結果

問題 No.3503 Brackets Stack Query 2
コンテスト
ユーザー Azaki
提出日時 2026-04-18 01:37:16
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 3,828 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,195 ms
コンパイル使用メモリ 166,164 KB
実行使用メモリ 8,188 KB
最終ジャッジ日時 2026-04-18 01:37:23
合計ジャッジ時間 6,177 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <string>

using namespace std;

/**
 * 良い棒付き括弧列
 * スタックを用いた (|) の逐次消去による判定
 */

int main() {
    // 入出力の高速化
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int Q;
    if (!(cin >> Q)) return 0;

    // stack には現在残っている文字を格納
    vector<char> st;
    // raw_history には、(|) による消去を「行わなかった場合」の
    // クエリ1で追加された実際の文字の履歴を保存（クエリ2の復元用）
    // もしくは、消去も含めたスタックの状態そのものを履歴に持ちます。
    
    // 最も確実なのは、各クエリ後のスタックの状態を「完全に復元可能」にすることです。
    // 各ステップでのスタックの「文字」と「消去されたかどうかのフラグ」を管理します。
    
    // 構造体でスタックの状態を管理
    struct State {
        char c;
    };
    vector<char> current_st;

    // クエリ2で「1つ前の状態」に戻す必要があるため、
    // 各クエリ直後のスタックを完全に保存するか、
    // 変更履歴（どの文字を追加したか、消去が発生したか）を記録します。
    
    // ここでは、各クエリ終了時のスタック全体を管理するのではなく、
    // 「追加された文字」をそのまま保持し、消去判定は表示上で行うか、
    // あるいはスタックの履歴を vector の vector で持つのはメモリを食い過ぎるので、
    // 以下のスタック管理が最も効率的です。

    vector<vector<char>> history; // メモリ制限に注意
    // Q=8*10^5 なので vector<vector> は MLE の危険があります。
    
    // --- 決定版アルゴリズム ---
    // スタックを1つ用意し、クエリ1なら文字を追加して (|) 判定。
    // クエリ2なら「直前のクエリ終了時のスタック」に戻す。
    // これを実現するために、スタックそのものの履歴ではなく
    // 「各時点でのスタックのトップポインタ」と「スタック配列」を永続化っぽく管理します。

    vector<char> data; // 物理的なスタックの中身
    vector<int> top_history; // 各クエリ終了時のスタックの「端」の位置
    top_history.push_back(0);
    data.reserve(Q);

    for (int q = 0; q < Q; ++q) {
        int type;
        cin >> type;

        if (type == 1) {
            char c;
            cin >> c;
            // 現在のスタックの状態をコピーして新しい文字を追加
            // (実際には前回の位置から継続)
            int current_top = top_history.back();
            
            // data の current_top の位置に新しい文字を書く
            if (data.size() <= current_top) {
                data.push_back(c);
            } else {
                data[current_top] = c;
            }
            current_top++;

            // 消去判定: (|) が並んだら top を 3 つ戻す
            if (current_top >= 3 && 
                data[current_top - 3] == '(' && 
                data[current_top - 2] == '|' && 
                data[current_top - 1] == ')') {
                current_top -= 3;
            }
            top_history.push_back(current_top);
        } else {
            // クエリ2: 1つ前のクエリの状態を捨てる
            if (!top_history.empty()) {
                top_history.pop_back();
            }
        }

        // 判定: スタックの長さ（top）が 0 なら Yes
        if (top_history.back() == 0) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }

    return 0;
}
0