結果

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

ソースコード

diff #
raw source code 

import sys
from array import array


def main() -> None:
    data = sys.stdin.buffer.read().split()
    if not data:
        return

    q = int(data[0])
    parent = array("I", [0]) * (q + 1)
    top = array("I", [0]) * (q + 1)
    ok = bytearray(q + 1)
    ok[0] = 1

    # Persistent parser-stack nodes.
    # state = 0: parsing the left S of "( S | S )"
    # state = 1: parsing the right S of "( S | S )"
    node_next = array("I", [0]) * (q + 1)
    node_state = bytearray(q + 1)

    cur = 0
    version_count = 0
    node_count = 0
    idx = 1
    out = []

    for _ in range(q):
        typ = data[idx]
        idx += 1

        if typ == b"1":
            ch = data[idx]
            idx += 1

            version_count += 1
            parent[version_count] = cur

            if ok[cur]:
                cur_top = top[cur]

                if ch == b"(":
                    node_count += 1
                    node_next[node_count] = cur_top
                    node_state[node_count] = 0
                    top[version_count] = node_count
                    ok[version_count] = 1
                elif ch == b"|":
                    if cur_top and node_state[cur_top] == 0:
                        node_count += 1
                        node_next[node_count] = node_next[cur_top]
                        node_state[node_count] = 1
                        top[version_count] = node_count
                        ok[version_count] = 1
                    else:
                        top[version_count] = 0
                        ok[version_count] = 0
                else:  # ch == b")"
                    if cur_top and node_state[cur_top] == 1:
                        top[version_count] = node_next[cur_top]
                        ok[version_count] = 1
                    else:
                        top[version_count] = 0
                        ok[version_count] = 0
            else:
                top[version_count] = 0
                ok[version_count] = 0

            cur = version_count
        else:
            cur = parent[cur]

        out.append("Yes\n" if ok[cur] and top[cur] == 0 else "No\n")

    sys.stdout.write("".join(out))


if __name__ == "__main__":
    main()
0