結果

問題 No.1778 括弧列クエリ / Bracketed Sequence Query
ユーザー WizistWizist
提出日時 2021-12-11 20:18:53
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,781 bytes
コンパイル時間 285 ms
コンパイル使用メモリ 86,968 KB
実行使用メモリ 151,888 KB
最終ジャッジ日時 2023-09-27 08:49:00
合計ジャッジ時間 26,874 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 816 ms
81,328 KB
testcase_01 AC 802 ms
80,520 KB
testcase_02 AC 791 ms
81,256 KB
testcase_03 AC 780 ms
80,916 KB
testcase_04 AC 800 ms
80,396 KB
testcase_05 AC 779 ms
106,892 KB
testcase_06 AC 558 ms
89,392 KB
testcase_07 AC 250 ms
95,020 KB
testcase_08 AC 1,446 ms
143,052 KB
testcase_09 AC 454 ms
110,592 KB
testcase_10 AC 792 ms
122,180 KB
testcase_11 AC 657 ms
115,016 KB
testcase_12 AC 804 ms
111,216 KB
testcase_13 AC 1,196 ms
140,852 KB
testcase_14 AC 724 ms
127,232 KB
testcase_15 AC 72 ms
71,356 KB
testcase_16 AC 1,226 ms
139,588 KB
testcase_17 AC 1,248 ms
145,812 KB
testcase_18 AC 1,305 ms
144,800 KB
testcase_19 AC 1,433 ms
145,180 KB
testcase_20 AC 1,738 ms
151,888 KB
testcase_21 AC 74 ms
71,536 KB
testcase_22 AC 73 ms
71,384 KB
testcase_23 AC 1,031 ms
119,012 KB
testcase_24 AC 1,071 ms
128,596 KB
testcase_25 AC 1,163 ms
128,804 KB
testcase_26 RE -
testcase_27 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

class LCA:
	def __init__(self, g, root=0):
		n, self.g, self.tick, self.anc, m = len(g), g, 0, [], len(g)
		self.tin, self.tout, self.pos, self.d, self.par = [0] * n, [0] * n, [0] * n, [0] * n, [-1] * n
		while m != 0: self.anc.append([0] * n); m //= 2
		def dfs(u):
			self.pos[self.tick] = u
			self.tin[u] = self.tick
			self.tick += 1
			self.anc[0][u] = max(self.par[u], 0)
			for i in range(1, len(self.anc)):
				self.anc[i][u] = self.anc[i - 1][self.anc[i - 1][u]]
			for v in self.g[u]:
				if self.par[u] != v:
					self.par[v] = u
					self.d[v] = self.d[u] + 1
					dfs(v)
			self.tout[u] = self.tick
		dfs(root)
	def is_ancestor(self, u, v):
		return self.tin[u] <= self.tin[v] and self.tout[u] >= self.tout[v]
	def lca(self, u, v):
		if self.is_ancestor(u, v): return u
		if self.is_ancestor(v, u): return v
		for i in range(len(self.anc) - 1, -1, -1):
			if not self.is_ancestor(self.anc[i][u], v): u = self.anc[i][u]
		return self.anc[0][u]
	def dist(self, u, v):
		return 0 if u == v else self.d[u] + self.d[v] - self.d[self.lca(u, v)] * 2
	def kth(self, u, k):	# k-th parent
		if k > self.d[u]: return -1
		i = 0
		while k > 0:
			if (k & 1) != 0: u = self.anc[i][u]
			k, i = k >> 1, i + 1
		return u

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