結果

問題 No.1778 括弧列クエリ / Bracketed Sequence Query
ユーザー roarisroaris
提出日時 2021-12-08 05:47:00
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,140 ms / 2,000 ms
コード長 2,312 bytes
コンパイル時間 542 ms
コンパイル使用メモリ 87,040 KB
実行使用メモリ 172,624 KB
最終ジャッジ日時 2023-09-22 19:42:45
合計ジャッジ時間 24,438 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 463 ms
86,372 KB
testcase_01 AC 461 ms
85,836 KB
testcase_02 AC 467 ms
85,696 KB
testcase_03 AC 476 ms
86,868 KB
testcase_04 AC 484 ms
86,008 KB
testcase_05 AC 607 ms
112,608 KB
testcase_06 AC 451 ms
87,076 KB
testcase_07 AC 199 ms
93,976 KB
testcase_08 AC 1,005 ms
149,396 KB
testcase_09 AC 412 ms
105,384 KB
testcase_10 AC 625 ms
148,236 KB
testcase_11 AC 556 ms
126,400 KB
testcase_12 AC 603 ms
112,360 KB
testcase_13 AC 961 ms
166,904 KB
testcase_14 AC 584 ms
140,604 KB
testcase_15 AC 95 ms
71,928 KB
testcase_16 AC 999 ms
149,468 KB
testcase_17 AC 1,033 ms
149,864 KB
testcase_18 AC 997 ms
149,704 KB
testcase_19 AC 1,038 ms
149,696 KB
testcase_20 AC 1,010 ms
149,608 KB
testcase_21 AC 93 ms
71,700 KB
testcase_22 AC 94 ms
71,728 KB
testcase_23 AC 786 ms
150,956 KB
testcase_24 AC 823 ms
170,164 KB
testcase_25 AC 911 ms
172,624 KB
testcase_26 AC 1,140 ms
152,524 KB
testcase_27 AC 413 ms
152,624 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