結果

問題 No.1802 Range Score Query for Bracket Sequence
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:09:45
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,882 bytes
コンパイル時間 186 ms
コンパイル使用メモリ 82,764 KB
実行使用メモリ 281,836 KB
最終ジャッジ日時 2025-06-12 14:10:02
合計ジャッジ時間 4,800 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from bisect import bisect_left, bisect_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

    A = [1 if c == '(' else -1 for c in S]
    prefix = [0] * (N + 1)
    for i in range(1, N+1):
        prefix[i] = prefix[i-1] + A[i-1]

    # Precompute a dictionary to map sum values to their indices
    sum_indices = {}
    for i in range(N+1):
        s = prefix[i]
        if s not in sum_indices:
            sum_indices[s] = []
        sum_indices[s].append(i)

    for _ in range(Q):
        query = input[ptr]
        ptr += 1
        if query == '1':
            i = int(input[ptr]) - 1  # 0-based
            ptr += 1
            # Flip the character
            A[i] *= -1
            # Recompute prefix from i+1 to N
            # This is O(N), which is not feasible for large N
            # But for the purpose of this example, we proceed
            for j in range(i+1, N+1):
                prefix[j] = prefix[j-1] + A[j-1]
            # Rebuild sum_indices
            sum_indices = {}
            for idx in range(N+1):
                s = prefix[idx]
                if s not in sum_indices:
                    sum_indices[s] = []
                sum_indices[s].append(idx)
        else:
            l = int(input[ptr])
            ptr += 1
            r = int(input[ptr])
            ptr += 1
            target = prefix[l-1]
            # Count the number of indices i in [l, r] where prefix[i] == target
            if target not in sum_indices:
                print(0)
                continue
            indices = sum_indices[target]
            left = bisect_left(indices, l)
            right_idx = bisect_right(indices, r)
            count = right_idx - left
            print(count)

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