結果

問題 No.3503 Brackets Stack Query 2
コンテスト
ユーザー Azaki
提出日時 2026-04-18 01:43:21
言語 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,252 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,119 ms
コンパイル使用メモリ 158,496 KB
実行使用メモリ 10,624 KB
最終ジャッジ日時 2026-04-18 01:43:30
合計ジャッジ時間 5,135 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>

using namespace std;

// 各クエリ終了時点の状態を保存する構造体
struct State {
    int st_ptr;   // スタックの長さ
    char last_c;  // スタックの末尾に追加された文字
};

const int MAXQ = 800005;
char st[MAXQ];      // 簡約化されたスタック本体
State history[MAXQ]; // 各ステップの状態履歴

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int Q;
    cin >> Q;

    int st_ptr = 0;
    // history[0] は空の状態
    history[0] = {0, '\0'};

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

        if (type == 1) {
            char c;
            cin >> c;

            // 1. 現在のスタックの末尾に文字を追加
            st[st_ptr] = c;
            st_ptr++;

            // 2. (|) が完成したら削除
            if (st_ptr >= 3 && 
                st[st_ptr - 3] == '(' && 
                st[st_ptr - 2] == '|' && 
                st[st_ptr - 1] == ')') {
                st_ptr -= 3;
            }

            // 3. このステップ終了時のスタックポインタを保存
            // 削除された場合でも、その時の st_ptr を記録しておく
            history[i] = {st_ptr, (st_ptr > 0 ? st[st_ptr - 1] : '\0')};
        } else {
            // クエリ2: 文字列Sの末尾を削除 = 1つ前のクエリ終了時の状態に戻す
            // 直前のクエリが「追加」だった場合、その追加分をなかったことにする
            history[i] = history[i - 1]; // 履歴を戻すのではなく、i-1時点の状態をiにも適用
            
            // 実際には「Sの末尾を消す」＝「クエリの履歴を1つ巻き戻す」ことなので
            // 内部的なポインタを i-1 の状態にセットするだけです
            st_ptr = history[i-1].st_ptr;
            
            // 注意：この問題のクエリ2は「直前のクエリ」を消すのではなく
            // 「現在の文字列S」の末尾を消す操作です。
            // 履歴管理を「文字列Sの長さ」に対して行う必要があります。
        }
    }
    // ... (以下解説)
}
0