結果

問題 No.1778 括弧列クエリ / Bracketed Sequence Query
コンテスト
ユーザー LyricalMaestro
提出日時 2026-11-05 02:28:32
言語 PyPy3
(8.0.1 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 477 ms / 2,000 ms
+ 759µs
コード長 2,042 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 107 ms
コンパイル使用メモリ 64,660 KB
実行使用メモリ 123,072 KB
最終ジャッジ日時 2026-11-05 02:29:04
合計ジャッジ時間 14,842 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

## https://yukicoder.me/problems/no/1778

from collections import deque

def main():
    N, Q = map(int, input().split())
    S = input()

    xy = []
    for _ in range(Q):
        x, y = map(int, input().split())
        xy.append((x, y))

    # 木を構成する
    in_map = {0:-1}
    out_map = {}
    k = 0
    parents = {0:-1}
    depth = {0: 0}
    for i in range(N):
        s = S[i]
        if s == "(":
            in_map[i + 1] = -1
            parents[i + 1] = k
            depth[i + 1] = depth[k] + 1
            k = i + 1
        else:
            in_map[k] = i + 1
            out_map[i + 1] = k
            k = parents[k]

    # parents_list = 
    k = 0
    while (1 << k) < N:
        k += 1
    max_k = k
    parents_list = [[-1] * N for _ in range(max_k + 1)]
    for c, p in parents.items():
        parents_list[0][c] = p
    for k in range(1, max_k + 1):
        for i in range(N):
            p = parents_list[k - 1][i]
            if p != -1:
                parents_list[k][i] = parents_list[k - 1][p]

    for x, y in xy:
        if x in out_map:
            x = out_map[x]
        if y in out_map:
            y = out_map[y]

        d_x = depth[x]
        d_y = depth[y]
        if d_x > d_y:
            x, y, d_x, d_y = y, x, d_y, d_x
        # d_x <= d_yを仮定する
        if d_x < d_y:
            for k in reversed(range(max_k + 1)):
                if d_y - (1 << k) >= d_x and parents_list[k][y] != -1:
                    y = parents_list[k][y]
                    d_y -= (1 << k)

        if x == y:
            answer= x
        else:
            d = d_x
            for k in reversed(range(max_k + 1)):
                if d >= (1 << k) and parents_list[k][x] != parents_list[k][y]:
                    x = parents_list[k][x]
                    y = parents_list[k][y]
                    d -= (1 << k)
            answer = parents_list[0][x]

        if answer == 0:
            print(-1)
        else:
            print(answer, in_map[answer])




 




 
if __name__ == "__main__":
    main()
0