結果

問題 No.1778 括弧列クエリ / Bracketed Sequence Query
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:20:42
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,883 bytes
コンパイル時間 342 ms
コンパイル使用メモリ 82,344 KB
実行使用メモリ 145,628 KB
最終ジャッジ日時 2025-03-31 17:22:11
合計ジャッジ時間 40,495 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21 TLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegmentTreeNode:
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.left = None
        self.right = None
        self.max_r = -1

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

def get_max(node, l, r):
    if node.end < l or node.start > r:
        return -1
    if l <= node.start and node.end <= r:
        return node.max_r
    left_max = get_max(node.left, l, r) if node.left else -1
    right_max = get_max(node.right, l, r) if node.right else -1
    return max(left_max, right_max)

def query_max_j(node, query_l, query_r, M):
    if node.end < query_l or node.start > query_r:
        return -1
    if node.max_r < M:
        return -1
    if node.start == node.end:
        return node.start
    res_right = query_max_j(node.right, query_l, query_r, M)
    if res_right != -1:
        return res_right
    return query_max_j(node.left, query_l, query_r, M)

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

    # Preprocess matching pairs
    match = [0]*(N+2)
    stack = []
    pairs = []
    for i in range(1, N+1):
        c = S[i-1]
        if c == '(':
            stack.append(i)
        else:
            j = stack.pop()
            match[j] = i
            match[i] = j
            pairs.append( (j, i) )
    pairs.sort()
    R = [ r for l, r in pairs ]
    len_R = len(R)
    if len_R == 0:
        root = None
    else:
        root = build_segment_tree(R, 0, len_R-1)

    # Process each query
    for _ in range(Q):
        x = int(data[idx])
        idx +=1
        y = int(data[idx])
        idx +=1

        x2 = match[x]
        y2 = match[y]
        m_min = min(x, x2, y, y2)
        m_max = max(x, x2, y, y2)

        # Binary search for the largest i where pairs[i][0] <= m_min
        low = 0
        high = len(pairs) -1
        i_max = -1
        while low <= high:
            mid = (low + high) // 2
            if pairs[mid][0] <= m_min:
                i_max = mid
                low = mid +1
            else:
                high = mid -1

        if i_max == -1:
            print(-1)
            continue

        # Check if max R in [0..i_max] >= m_max
        max_r_val = get_max(root, 0, i_max)
        if max_r_val < m_max:
            print(-1)
            continue

        j = query_max_j(root, 0, i_max, m_max)
        if j == -1:
            print(-1)
        else:
            print(pairs[j][0], pairs[j][1])

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