結果

問題 No.1778 括弧列クエリ / Bracketed Sequence Query
コンテスト
ユーザー lam6er
提出日時 2025-04-15 23:48:11
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,972 bytes
コンパイル時間 158 ms
コンパイル使用メモリ 82,116 KB
実行使用メモリ 133,784 KB
最終ジャッジ日時 2025-04-15 23:50:06
合計ジャッジ時間 17,256 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 8 WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import bisect

class SegmentTreeNode:
    def __init__(self, l, r):
        self.l = l
        self.r = r
        self.left_child = None
        self.right_child = None
        self.max_R = -1
        self.max_R_L = -1

def build_segment_tree(l, r, L_list, match):
    node = SegmentTreeNode(l, r)
    if l == r:
        current_L = L_list[l]
        node.max_R = match[current_L]
        node.max_R_L = current_L
    else:
        mid = (l + r) // 2
        node.left_child = build_segment_tree(l, mid, L_list, match)
        node.right_child = build_segment_tree(mid+1, r, L_list, match)
        if node.left_child.max_R >= node.right_child.max_R:
            node.max_R = node.left_child.max_R
            node.max_R_L = node.left_child.max_R_L
        else:
            node.max_R = node.right_child.max_R
            node.max_R_L = node.right_child.max_R_L
    return node

def query_max_L(node, query_l, query_r, right_max):
    if node.r < query_l or node.l > query_r:
        return -1
    if node.max_R < right_max:
        return -1
    if query_l <= node.l and node.r <= query_r:
        if node.l == node.r:
            return node.max_R_L if node.max_R >= right_max else -1
        res_right = query_max_L(node.right_child, query_l, query_r, right_max)
        if res_right != -1:
            return res_right
        if node.max_R >= right_max:
            return node.max_R_L
        res_left = query_max_L(node.left_child, query_l, query_r, right_max)
        return res_left
    else:
        res_right = query_max_L(node.right_child, query_l, query_r, right_max)
        if res_right != -1:
            return res_right
        res_left = query_max_L(node.left_child, query_l, query_r, right_max)
        return res_left if res_left != -1 else res_right

def main():
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr += 1
    q = int(input[ptr])
    ptr += 1
    s = input[ptr]
    ptr += 1

    match = [0] * (n + 2)
    stack = []
    L_list = []
    for i in range(1, n + 1):
        if s[i - 1] == '(':
            stack.append(i)
            L_list.append(i)
        else:
            if stack:
                j = stack.pop()
                match[j] = i
                match[i] = j

    if not L_list:
        for _ in range(q):
            print(-1)
        return

    m = len(L_list)
    root = build_segment_tree(0, m - 1, L_list, match)

    for _ in range(q):
        x = int(input[ptr])
        ptr += 1
        y = int(input[ptr])
        ptr += 1
        mx = match[x]
        my = match[y]
        points = [x, mx, y, my]
        left_min = min(points)
        right_max = max(points)
        pos = bisect.bisect_right(L_list, left_min) - 1
        if pos < 0:
            print(-1)
            continue
        res_L = query_max_L(root, 0, pos, right_max)
        if res_L == -1:
            print(-1)
        else:
            print(res_L, match[res_L])

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