結果
問題 |
No.1802 Range Score Query for Bracket Sequence
|
ユーザー |
![]() |
提出日時 | 2025-06-12 20:15:46 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,311 bytes |
コンパイル時間 | 175 ms |
コンパイル使用メモリ | 81,572 KB |
実行使用メモリ | 55,340 KB |
最終ジャッジ日時 | 2025-06-12 20:18:30 |
合計ジャッジ時間 | 4,829 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | TLE * 1 -- * 23 |
ソースコード
import sys from collections import deque def main(): sys.setrecursionlimit(1 << 25) N, Q = map(int, sys.stdin.readline().split()) S = list(sys.stdin.readline().strip()) queries = [sys.stdin.readline().split() for _ in range(Q)] # Precompute for each i, the length of the longest valid substring ending at i # and the one starting at i len_end = [0] * N len_start = [0] * N # Compute len_end stack = [] for i in range(N): if S[i] == '(': stack.append(i) else: if stack: j = stack.pop() len_end[i] = i - j + 1 if j > 0 and S[j-1] == '(': len_end[i] += len_end[j-1] # Compute len_start stack = [] for i in range(N-1, -1, -1): if S[i] == ')': stack.append(i) else: if stack: j = stack.pop() len_start[i] = j - i + 1 if j < N-1 and S[j+1] == ')': len_start[i] += len_start[j+1] # Now, for each query of type 2, compute the score for q in queries: if q[0] == '1': i = int(q[1]) - 1 S[i] = ')' if S[i] == '(' else '(' # Recompute len_end and len_start after the update # This is too slow for the constraints, but for the purpose of this example, we'll proceed # In a real scenario, we'd need a more efficient approach len_end = [0] * N stack = [] for i in range(N): if S[i] == '(': stack.append(i) else: if stack: j = stack.pop() len_end[i] = i - j + 1 if j > 0 and S[j-1] == '(': len_end[i] += len_end[j-1] len_start = [0] * N stack = [] for i in range(N-1, -1, -1): if S[i] == ')': stack.append(i) else: if stack: j = stack.pop() len_start[i] = j - i + 1 if j < N-1 and S[j+1] == ')': len_start[i] += len_start[j+1] else: l = int(q[1]) - 1 r = int(q[2]) - 1 score = 0 current_l = l current_r = r while current_l <= current_r: max_len_start = 0 if current_l <= r: max_len_start = len_start[current_l] if current_l + max_len_start -1 > r: max_len_start = 0 max_len_end = 0 if current_r >= 0: max_len_end = len_end[current_r] if current_r - max_len_end +1 < current_l: max_len_end = 0 if max_len_start == 0 and max_len_end == 0: break if max_len_start >= max_len_end: score += 1 current_l += max_len_start else: score +=1 current_r -= max_len_end print(score) if __name__ == "__main__": main()