結果

問題 No.1778 括弧列クエリ / Bracketed Sequence Query
ユーザー lam6er
提出日時 2025-04-16 16:28:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,220 ms / 2,000 ms
コード長 2,282 bytes
コンパイル時間 348 ms
コンパイル使用メモリ 82,076 KB
実行使用メモリ 144,192 KB
最終ジャッジ日時 2025-04-16 16:29:30
合計ジャッジ時間 21,020 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

class SegmentTreeNode:
    def __init__(self, l, r):
        self.l = l
        self.r = r
        self.left = None
        self.right = None
        self.max_j = 0

def build(l, r, j_values):
    node = SegmentTreeNode(l, r)
    if l == r:
        node.max_j = j_values[l]
    else:
        mid = (l + r) // 2
        node.left = build(l, mid, j_values)
        node.right = build(mid + 1, r, j_values)
        node.max_j = max(node.left.max_j, node.right.max_j)
    return node

def query_max(node, L, R, target):
    if node.r < L or node.l > R:
        return -1
    if node.max_j < target:
        return -1
    if node.l == node.r:
        return node.l
    res = query_max(node.right, L, R, target)
    if res != -1:
        return res
    return query_max(node.left, L, R, target)

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    N = int(data[ptr])
    ptr += 1
    Q = int(data[ptr])
    ptr += 1
    S = data[ptr]
    ptr += 1

    match = [0] * (N + 2)
    stack = []
    for i in range(1, N + 1):
        if S[i - 1] == '(':
            stack.append(i)
        else:
            if stack:
                left = stack.pop()
                match[left] = i
                match[i] = left

    left_brackets = []
    for i in range(1, N + 1):
        if S[i - 1] == '(':
            left_brackets.append(i)

    if not left_brackets:
        for _ in range(Q):
            print(-1)
        return

    j_values = [match[i] for i in left_brackets]
    root = build(0, len(left_brackets) - 1, j_values)

    output = []
    for _ in range(Q):
        x = int(data[ptr])
        ptr += 1
        y = int(data[ptr])
        ptr += 1

        mx = match[x]
        my = match[y]
        positions = [x, mx, y, my]
        min_pos = min(positions)
        max_pos = max(positions)

        pos = bisect.bisect_right(left_brackets, min_pos) - 1
        if pos < 0:
            output.append("-1")
            continue

        k = query_max(root, 0, pos, max_pos)
        if k == -1:
            output.append("-1")
        else:
            ans_i = left_brackets[k]
            ans_j = j_values[k]
            output.append(f"{ans_i} {ans_j}")

    print('\n'.join(output))

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