#include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int Q; cin >> Q; // 現在の「良い括弧列判定用」のスタック vector st; // total_history[i] = クエリ i 終了時点でのスタック st のコピー // ...はメモリ不足になるので、各ステップでの「変更内容」を記録します。 // st_history[i] : i番目の文字を追加/削除した直後の「スタックのサイズ」 vector st_size_history; st_size_history.push_back(0); // 実際のスタックの中身を保持(クエリ1で増える一方のメモリ) // ただし、消去されたらポインタを戻す vector 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; }