結果

問題 No.1778 括弧列クエリ / Bracketed Sequence Query
コンテスト
ユーザー roaris
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

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