結果

問題 No.1778 括弧列クエリ / Bracketed Sequence Query
ユーザー WizistWizist
提出日時 2021-12-11 20:15:11
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,505 bytes
コンパイル時間 177 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 113,888 KB
最終ジャッジ日時 2024-07-20 02:50:35
合計ジャッジ時間 33,529 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,096 ms
81,056 KB
testcase_01 AC 1,110 ms
82,488 KB
testcase_02 AC 1,084 ms
82,460 KB
testcase_03 AC 1,066 ms
82,012 KB
testcase_04 AC 1,137 ms
82,544 KB
testcase_05 AC 1,121 ms
96,480 KB
testcase_06 AC 892 ms
86,004 KB
testcase_07 AC 284 ms
84,816 KB
testcase_08 AC 1,584 ms
112,660 KB
testcase_09 AC 717 ms
93,924 KB
testcase_10 AC 1,064 ms
106,968 KB
testcase_11 AC 1,033 ms
99,444 KB
testcase_12 AC 1,167 ms
95,716 KB
testcase_13 AC 1,551 ms
109,344 KB
testcase_14 AC 1,048 ms
103,028 KB
testcase_15 AC 44 ms
52,864 KB
testcase_16 AC 1,591 ms
112,936 KB
testcase_17 AC 1,636 ms
111,924 KB
testcase_18 AC 1,630 ms
113,888 KB
testcase_19 AC 1,598 ms
112,920 KB
testcase_20 AC 1,569 ms
111,856 KB
testcase_21 AC 44 ms
52,992 KB
testcase_22 AC 43 ms
52,608 KB
testcase_23 AC 1,548 ms
102,912 KB
testcase_24 AC 1,591 ms
109,952 KB
testcase_25 AC 1,731 ms
109,952 KB
testcase_26 RE -
testcase_27 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

class LCA:
	def __init__(self, g, root=0):
		n, r, self.tick = len(g), [], 0
		self.n, self.t, self.d, self.p, self.q = n, [0] * n, [0] * n, [], [0] * (n * 2)
		def dfs(u, par):
			self.t[u] = self.tick; self.tick += 1
			for v in g[u]:
				if v != par: self.d[v] = self.d[u] + 1; self.p.append(u); r.append(self.t[u]); dfs(v, u)
		dfs(root, -1)
		for i, val in enumerate(r):
			self.q[i + n], j = val, (i + n) >> 1
			while j != 0: self.q[j] = min(self.q[j * 2], self.q[j * 2 + 1]); j >>= 1
	def rmq(self, l, r):
		i, j, a, b = l + self.n, r + self.n, float('inf'), float('inf')
		while i < j:
			if i & 1: a = min(a, self.q[i]); i += 1
			if j & 1: j -= 1; b = min(b, self.q[j])
			i, j = i // 2, j // 2
		return min(a, b)
	def lca(self, u, v):
		return u if u == v else self.p[self.rmq(min(self.t[u], self.t[v]), max(self.t[u], self.t[v]))]
	def dist(self, u, v):
		return 0 if u == v else self.d[u] + self.d[v] - self.d[self.lca(u, v)] * 2

from bisect import bisect_left

N, Q = map(int, input().split())
s = '(' + input().strip() + ')'
n = N + 2
p, st = [0] * n, []
for i, x in enumerate(s):
	if x == '(':
		st.append(i)
	else:
		p[i] = st[-1]
		p[st[-1]] = i
		st.pop()
g = [[] for _ in range(n)]

def build(u, c):
	if c <= 2: return
	v = u + 1
	while v < u + c and p[v] > v:
		g[u].append(v)
		build(v, p[v] - v + 1)
		v = p[v] + 1
build(0, n)

lca = LCA(g)

for _ in range(Q):
	x, y = map(int, input().split())
	t = lca.lca(min(x, p[x]), min(y, p[y]))
	if t == 0: print(-1)
	else: print(t, p[t])
0