結果

問題 No.1778 括弧列クエリ / Bracketed Sequence Query
ユーザー lam6er
提出日時 2025-04-15 23:45:40
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,784 bytes
コンパイル時間 216 ms
コンパイル使用メモリ 82,352 KB
実行使用メモリ 141,140 KB
最終ジャッジ日時 2025-04-15 23:48:45
合計ジャッジ時間 38,933 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21 TLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.data = data
        self.tree = [0] * (4 * self.n)
        self.build(0, 0, self.n - 1)
    
    def build(self, node, l, r):
        if l == r:
            self.tree[node] = self.data[l]
            return
        mid = (l + r) // 2
        left = 2 * node + 1
        right = 2 * node + 2
        self.build(left, l, mid)
        self.build(right, mid + 1, r)
        self.tree[node] = max(self.tree[left], self.tree[right])
    
    def query_max(self, l, r):
        return self._query_max(0, 0, self.n - 1, l, r)
    
    def _query_max(self, node, node_l, node_r, l, r):
        if node_r < l or node_l > r:
            return -float('inf')
        if l <= node_l and node_r <= r:
            return self.tree[node]
        mid = (node_l + node_r) // 2
        left_val = self._query_max(2 * node + 1, node_l, mid, l, r)
        right_val = self._query_max(2 * node + 2, mid + 1, node_r, l, r)
        return max(left_val, right_val)
    
    def find_max_index(self, k, M):
        return self._find_max_index(0, 0, self.n - 1, k, M)
    
    def _find_max_index(self, node, node_l, node_r, k, M):
        if node_r > k:
            mid = (node_l + node_r) // 2
            left_child = 2 * node + 1
            right_child = 2 * node + 2
            if mid + 1 > k:
                return self._find_max_index(left_child, node_l, mid, k, M)
            else:
                res_right = self._find_max_index(right_child, mid + 1, node_r, k, M)
                if res_right != -1:
                    return res_right
                res_left = self._find_max_index(left_child, node_l, mid, k, M)
                return res_left
        else:
            if self.tree[node] < M:
                return -1
            if node_l == node_r:
                return node_l if self.data[node_l] >= M else -1
            mid = (node_l + node_r) // 2
            left_child = 2 * node + 1
            right_child = 2 * node + 2
            res_right = self._find_max_index(right_child, mid + 1, node_r, k, M)
            if res_right != -1:
                return res_right
            res_left = self._find_max_index(left_child, node_l, mid, k, M)
            return res_left

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    Q = int(input[ptr])
    ptr += 1
    S = input[ptr]
    ptr += 1
    
    pair = [0] * N
    stack = []
    for i in range(N):
        if S[i] == '(':
            stack.append(i)
        else:
            j = stack.pop()
            pair[j] = i
            pair[i] = j
    
    bracket_pairs = []
    for i in range(N):
        if i < pair[i]:
            bracket_pairs.append((i, pair[i]))
    
    bracket_pairs.sort()
    L_list = [bp[0] for bp in bracket_pairs]
    R_list = [bp[1] for bp in bracket_pairs]
    
    st = None
    if bracket_pairs:
        st = SegmentTree(R_list)
    
    for _ in range(Q):
        x = int(input[ptr]) - 1
        ptr += 1
        y = int(input[ptr]) - 1
        ptr += 1
        
        x_match = pair[x]
        y_match = pair[y]
        positions = [x, x_match, y, y_match]
        m = min(positions)
        M = max(positions)
        
        if not bracket_pairs:
            print(-1)
            continue
        
        k = bisect.bisect_right(L_list, m) - 1
        if k < 0:
            print(-1)
            continue
        
        max_r = st.query_max(0, k)
        if max_r < M:
            print(-1)
            continue
        
        i = st.find_max_index(k, M)
        if i == -1:
            print(-1)
        else:
            L, R = bracket_pairs[i]
            print(L + 1, R + 1)

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