結果

問題 No.1802 Range Score Query for Bracket Sequence
コンテスト
ユーザー gew1fw
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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()
0