結果

問題 No.1778 括弧列クエリ / Bracketed Sequence Query
ユーザー roarisroaris
提出日時 2021-12-08 05:47:00
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,254 ms / 2,000 ms
コード長 2,312 bytes
コンパイル時間 837 ms
コンパイル使用メモリ 82,236 KB
実行使用メモリ 168,896 KB
最終ジャッジ日時 2024-07-08 10:32:17
合計ジャッジ時間 24,551 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 454 ms
83,400 KB
testcase_01 AC 442 ms
83,224 KB
testcase_02 AC 448 ms
83,668 KB
testcase_03 AC 447 ms
84,076 KB
testcase_04 AC 454 ms
83,868 KB
testcase_05 AC 639 ms
100,588 KB
testcase_06 AC 439 ms
85,232 KB
testcase_07 AC 161 ms
92,544 KB
testcase_08 AC 1,063 ms
159,744 KB
testcase_09 AC 377 ms
103,808 KB
testcase_10 AC 658 ms
136,480 KB
testcase_11 AC 588 ms
115,064 KB
testcase_12 AC 678 ms
101,144 KB
testcase_13 AC 1,036 ms
158,720 KB
testcase_14 AC 603 ms
128,812 KB
testcase_15 AC 46 ms
54,400 KB
testcase_16 AC 1,068 ms
159,616 KB
testcase_17 AC 1,106 ms
159,744 KB
testcase_18 AC 1,115 ms
159,616 KB
testcase_19 AC 1,097 ms
159,976 KB
testcase_20 AC 1,084 ms
159,616 KB
testcase_21 AC 48 ms
54,272 KB
testcase_22 AC 47 ms
53,888 KB
testcase_23 AC 831 ms
122,240 KB
testcase_24 AC 859 ms
146,656 KB
testcase_25 AC 937 ms
145,996 KB
testcase_26 AC 1,254 ms
168,896 KB
testcase_27 AC 417 ms
168,856 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
from collections import *

class LCA:
    def __init__(self, N, G, roots):
        self.N = N
        self.G = G
        self.log_size = 22
        self.par = [[-1]*self.N for _ in range(self.log_size)]
        q = deque(roots)
        self.dep = [-1]*self.N
        
        for r in roots:
            self.dep[r] = 0
        
        while q:
            v = q.popleft()
            
            for nv in self.G[v]:
                if self.dep[nv]==-1:
                    self.par[0][nv] = v
                    self.dep[nv] = self.dep[v]+1
                    q.append(nv)
                    
        for i in range(1, self.log_size):
            for v in range(self.N):
                if self.par[i-1][v]>=0:
                    self.par[i][v] = self.par[i-1][self.par[i-1][v]]
    
    def calc_lca(self, u, v):
        if self.dep[u]>self.dep[v]:
            u, v = v, u
        
        for i in range(self.log_size):
            if ((self.dep[v]-self.dep[u])>>i)&1:
                v = self.par[i][v]
        
        if u==v:
            return u
        
        for i in range(self.log_size-1, -1, -1):
            if self.par[i][u]!=self.par[i][v]:
                u, v = self.par[i][u], self.par[i][v]
        
        if self.par[0][u]!=self.par[0][v]:
            return -1
            
        return self.par[0][u]

N, Q = map(int, input().split())
S = input()[:-1]
G = [[] for _ in range(N//2)]
serial = 0
to_i = defaultdict(int)
to_v = defaultdict(int)
to_l = defaultdict(int)
to_r = defaultdict(int)
pars = []
roots = []
ls = []

for i in range(N):
    if S[i]=='(':
        if len(pars)==0:
            roots.append(serial)
        else:
            par = pars[-1]
            G[par].append(serial)
        
        to_i[serial] = i
        to_v[i] = serial
        pars.append(serial)
        serial += 1
        ls.append(i)
    else:
        l = ls.pop()
        pars.pop()
        to_l[i] = l
        to_r[l] = i

lca = LCA(N//2, G, roots)

for _ in range(Q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    xl = x if x in to_r else to_l[x]
    yl = y if y in to_r else to_l[y]
    v = lca.calc_lca(to_v[xl], to_v[yl])
    
    if v==-1:
        print(-1)
    else:
        l = to_i[v]
        r = to_r[l]
        print(l+1, r+1)
0