結果

問題 No.3503 Brackets Stack Query 2
コンテスト
ユーザー praddumna12
提出日時 2026-04-18 04:30:09
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
WA  
実行時間 -
コード長 2,183 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,095 ms
コンパイル使用メモリ 20,700 KB
実行使用メモリ 62,684 KB
最終ジャッジ日時 2026-04-18 04:30:54
合計ジャッジ時間 40,368 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 19 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

Q = int(input())

stack = []
history = []
invalid = 0

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

    if query[0] == '1':
        c = query[1]

        if c == '(':
            stack.append([False, True])  # has_bar, valid
            history.append(('push',))

        elif c == '|':
            if stack:
                old = stack[-1][0]
                stack[-1][0] = True
                history.append(('bar', old))
            else:
                history.append(('bar_empty',))

        else:  # ')'
            if not stack:
                invalid += 1
                history.append(('bad_close',))
            else:
                has_bar, valid = stack.pop()

                was_invalid = False
                if not has_bar or not valid:
                    invalid += 1
                    was_invalid = True

                if stack:
                    parent = stack[-1]
                    old_bar = parent[0]
                    old_valid = parent[1]

                    parent[0] |= has_bar
                    parent[1] &= valid

                    history.append(('pop_merge', has_bar, valid,
                                    old_bar, old_valid, was_invalid))
                else:
                    history.append(('pop_root', has_bar, valid, was_invalid))

    else:
        op = history.pop()

        if op[0] == 'push':
            stack.pop()

        elif op[0] == 'bar':
            stack[-1][0] = op[1]

        elif op[0] == 'bar_empty':
            pass

        elif op[0] == 'bad_close':
            invalid -= 1

        elif op[0] == 'pop_merge':
            has_bar, valid, old_bar, old_valid, was_invalid = op[1:]

            parent = stack[-1]
            parent[0] = old_bar
            parent[1] = old_valid

            if was_invalid:
                invalid -= 1

            stack.append([has_bar, valid])

        elif op[0] == 'pop_root':
            has_bar, valid, was_invalid = op[1:]

            if was_invalid:
                invalid -= 1

            stack.append([has_bar, valid])

    if invalid == 0 and not stack:
        print("Yes")
    else:
        print("No")
0