結果

問題 No.1778 括弧列クエリ / Bracketed Sequence Query
ユーザー lam6er
提出日時 2025-03-20 20:32:33
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,789 ms / 2,000 ms
コード長 3,553 bytes
コンパイル時間 343 ms
コンパイル使用メモリ 82,632 KB
実行使用メモリ 135,908 KB
最終ジャッジ日時 2025-03-20 20:33:51
合計ジャッジ時間 33,903 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import bisect

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

    stack = []
    match = [0] * (N + 2)  # 1-based indexing

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

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

    pairs.sort()
    if not pairs:
        for _ in range(Q):
            print(-1)
        return

    M = len(pairs)
    R = [r for l, r in pairs]

    class SegmentTree:
        def __init__(self, data):
            self.n = len(data)
            self.tree = [0] * (4 * self.n)
            self.build(0, 0, self.n - 1, data)

        def build(self, node, l, r, data):
            if l == r:
                self.tree[node] = data[l]
            else:
                mid = (l + r) // 2
                self.build(2 * node + 1, l, mid, data)
                self.build(2 * node + 2, mid + 1, r, data)
                self.tree[node] = max(self.tree[2 * node + 1], self.tree[2 * node + 2])

        def query_max(self, l, r, node=0, node_l=0, node_r=None):
            if node_r is None:
                node_r = self.n - 1
            if r < node_l or l > node_r:
                return -1
            if l <= node_l and node_r <= r:
                return self.tree[node]
            mid = (node_l + node_r) // 2
            left = self.query_max(l, r, 2 * node + 1, node_l, mid)
            right_val = self.query_max(l, r, 2 * node + 2, mid + 1, node_r)
            return max(left, right_val)

        def find_rightmost(self, k, y):
            return self._find_rightmost(0, 0, self.n - 1, k, y)

        def _find_rightmost(self, node, node_l, node_r, k, y):
            if node_r > k:
                mid = (node_l + node_r) // 2
                res = -1
                if mid + 1 <= k:
                    if self.tree[2 * node + 2] >= y:
                        res = self._find_rightmost(2 * node + 2, mid + 1, node_r, k, y)
                if res != -1:
                    return res
                if self.tree[2 * node + 1] >= y:
                    return self._find_rightmost(2 * node + 1, node_l, mid, k, y)
                return -1
            else:
                if self.tree[node] < y:
                    return -1
                if node_l == node_r:
                    return node_l if R[node_l] >= y else -1
                mid = (node_l + node_r) // 2
                res_right = self._find_rightmost(2 * node + 2, mid + 1, node_r, k, y)
                if res_right != -1:
                    return res_right
                return self._find_rightmost(2 * node + 1, node_l, mid, k, y)

    st = SegmentTree(R)

    Ls = [l for l, r in pairs]

    for _ in range(Q):
        x = int(input[ptr])
        y = int(input[ptr + 1])
        ptr += 2
        a = match[x]
        b = match[y]
        points = [x, a, y, b]
        min_p = min(points)
        max_p = max(points)
        k = bisect.bisect_right(Ls, min_p) - 1
        if k < 0:
            print(-1)
            continue
        if st.query_max(0, k) < max_p:
            print(-1)
            continue
        ans_i = st.find_rightmost(k, max_p)
        if ans_i == -1:
            print(-1)
        else:
            l, r = pairs[ans_i]
            print(l, r)

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