結果

問題 No.3503 Brackets Stack Query 2
コンテスト
ユーザー R1yhtp
提出日時 2026-04-18 00:58:50
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
AC  
実行時間 776 ms / 2,000 ms
コード長 1,839 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 580 ms
コンパイル使用メモリ 20,960 KB
実行使用メモリ 63,584 KB
最終ジャッジ日時 2026-04-18 00:59:21
合計ジャッジ時間 23,880 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

input = sys.stdin.readline

Q = int(input())

# 可持久化栈结点
# 结点 0 表示空栈
stage = [0]   # stage[i] = 0 / 1
nxt = [0]     # nxt[i] = 下一个结点编号

# 当前字符串每个长度对应的状态
# tops[-1] / oks[-1] 就是当前 S 的状态
tops = [0]        # 栈顶结点编号
oks = [True]      # 当前前缀是否仍然可能合法

ans = []

for _ in range(Q):
    q = input().split()

    if q[0] == '1':
        c = q[1]
        top = tops[-1]
        ok = oks[-1]

        if not ok:
            # 已经错了，继续追加也不可能恢复
            tops.append(top)
            oks.append(False)

        else:
            if c == '(':
                # 压入阶段 0
                stage.append(0)
                nxt.append(top)
                tops.append(len(stage) - 1)
                oks.append(True)

            elif c == '|':
                # 栈顶必须是阶段 0
                if top == 0 or stage[top] == 1:
                    tops.append(top)
                    oks.append(False)
                else:
                    # 把栈顶从 0 变成 1（持久化做法：新建一个点）
                    stage.append(1)
                    nxt.append(nxt[top])
                    tops.append(len(stage) - 1)
                    oks.append(True)

            else:  # c == ')'
                # 栈顶必须是阶段 1
                if top == 0 or stage[top] == 0:
                    tops.append(top)
                    oks.append(False)
                else:
                    # 弹栈
                    tops.append(nxt[top])
                    oks.append(True)

    else:
        # 删除末尾字符：直接回退一个状态
        tops.pop()
        oks.pop()

    ans.append("Yes" if oks[-1] and tops[-1] == 0 else "No")

print("\n".join(ans))
0