結果

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

ソースコード

diff #
raw source code 

import sys

input = sys.stdin.readline

q = int(input())

# stack node: (state, next_node)
# state 0 = saw '(' but not '|'
# state 1 = saw '(' and then '|', waiting for ')'
state = [-1]
nxt = [0]

def make_node(v, to):
    state.append(v)
    nxt.append(to)
    return len(state) - 1

top_at_len = [0] * (q + 1)
ok_at_len = [True] * (q + 1)

cur_len = 0
out = []

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

    if line[0] == "1":
        ch = line[1]
        prev_len = cur_len
        cur_len += 1

        if not ok_at_len[prev_len]:
            ok_at_len[cur_len] = False
            top_at_len[cur_len] = 0
        else:
            top = top_at_len[prev_len]

            if ch == "(":
                ok_at_len[cur_len] = True
                top_at_len[cur_len] = make_node(0, top)

            elif ch == "|":
                if top != 0 and state[top] == 0:
                    ok_at_len[cur_len] = True
                    top_at_len[cur_len] = make_node(1, nxt[top])
                else:
                    ok_at_len[cur_len] = False
                    top_at_len[cur_len] = 0

            else:  # ')'
                if top != 0 and state[top] == 1:
                    ok_at_len[cur_len] = True
                    top_at_len[cur_len] = nxt[top]
                else:
                    ok_at_len[cur_len] = False
                    top_at_len[cur_len] = 0

    else:
        cur_len -= 1

    if ok_at_len[cur_len] and top_at_len[cur_len] == 0:
        out.append("Yes")
    else:
        out.append("No")

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