結果
問題 |
No.1802 Range Score Query for Bracket Sequence
|
ユーザー |
![]() |
提出日時 | 2025-06-12 19:14:50 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,882 bytes |
コンパイル時間 | 184 ms |
コンパイル使用メモリ | 82,472 KB |
実行使用メモリ | 53,016 KB |
最終ジャッジ日時 | 2025-06-12 19:15:19 |
合計ジャッジ時間 | 4,800 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | TLE * 1 -- * 23 |
ソースコード
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()