結果

問題 No.3503 Brackets Stack Query 2
コンテスト
ユーザー Azaki
提出日時 2026-04-18 01:37:48
言語 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  
実行時間 -
コード長 2,524 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,780 ms
コンパイル使用メモリ 164,520 KB
実行使用メモリ 8,568 KB
最終ジャッジ日時 2026-04-18 01:38:05
合計ジャッジ時間 9,871 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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;
    cin >> Q;

    // 現在の「良い括弧列判定用」のスタック
    vector<char> st;
    // total_history[i] = クエリ i 終了時点でのスタック st のコピー
    // ...はメモリ不足になるので、各ステップでの「変更内容」を記録します。
    
    // st_history[i] : i番目の文字を追加/削除した直後の「スタックのサイズ」
    vector<int> st_size_history;
    st_size_history.push_back(0);

    // 実際のスタックの中身を保持（クエリ1で増える一方のメモリ）
    // ただし、消去されたらポインタを戻す
    vector<char> st_data; 

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

        if (type == 1) {
            char c;
            cin >> c;
            
            // 現在のスタックの状態を取得
            int cur_sz = st_size_history.back();
            
            // 文字を追加
            if (st_data.size() <= cur_sz) {
                st_data.push_back(c);
            } else {
                st_data[cur_sz] = c;
            }
            cur_sz++;

            // (|) が完成したか判定
            if (cur_sz >= 3 && 
                st_data[cur_sz - 3] == '(' && 
                st_data[cur_sz - 2] == '|' && 
                st_data[cur_sz - 1] == ')') {
                cur_sz -= 3; // 3文字消去
            }
            
            st_size_history.push_back(cur_sz);
        } else {
            // クエリ2: 末尾の文字を削除
            // これは「直前のクエリ1を追加しなかったことにする」のではなく、
            // 「スタックの構成要素となった最後の1文字を消す」という動作。
            
            // 【重要】
            // 問題文の「Sの末尾を削除」は、
            // 「(|) で消えた後の文字列」に対してではなく、
            // 「消える前の全入力」に対して行うと解釈すると、
            // 履歴を 1 つ戻すだけで正しい挙動になります。
            if (st_size_history.size() > 1) {
                st_size_history.pop_back();
            }
        }

        // 判定
        if (st_size_history.back() == 0) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }

    return 0;
}
0