結果

問題 No.3503 Brackets Stack Query 2
コンテスト
ユーザー tnakao0123
提出日時 2026-04-20 13:05:17
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 93 ms / 2,000 ms
コード長 1,460 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 366 ms
コンパイル使用メモリ 69,808 KB
実行使用メモリ 25,512 KB
最終ジャッジ日時 2026-04-20 13:05:29
合計ジャッジ時間 7,806 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/* -*- coding: utf-8 -*-
 *
 * 3503.cc:  No.3503 Brackets Stack Query 2 - yukicoder
 */

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

/* constant */

const int MAX_N = 800000;

/* typedef */

using vc = vector<char>;

/* global variables */

bool fs[MAX_N + 1];
vc cvs[MAX_N];

/* subroutines */

/* main */

int main() {
  int qn;
  scanf("%d", &qn);

  int d = -1, n = 0;
  vc s;
  fs[0] = true;
  
  while (qn--) {
    int op;
    scanf("%d", &op);

    if (op == 1) {
      char cs[4];
      scanf("%s", cs);
      char c = cs[0];

      if (! fs[n]) fs[n + 1] = false;
      else {
	if (c == '(') {
	  d++;
	  cvs[d].push_back(c);
	  s.push_back(c);
	  fs[n + 1] = true;
	}
	else if (c == '|') {
	  if (d >= 0 && ! cvs[d].empty() && cvs[d].back() == '(') {
	    cvs[d].push_back(c);
	    s.push_back(c);
	    fs[n + 1] = true;
	  }
	  else
	    fs[n + 1] = false;
	}
	else { // c == ')'
	  if (d >= 0 && ! cvs[d].empty() && cvs[d].back() == '|') {
	    cvs[d].push_back(c);
	    d--;
	    s.push_back(c);
	    fs[n + 1] = true;
	  }
	  else
	    fs[n + 1] = false;
	}
      }
      n++;
    }
    else { // op == 2
      if (fs[n]) {
	char c = s.back(); s.pop_back();

	if (c == '(') {
	  cvs[d].pop_back();
	  d--;
	}
	else if (c == '|') {
	  cvs[d].pop_back();
	}
	else { // c == ')'
	  d++;
	  cvs[d].pop_back();
	}
      }
      n--;
    }

    if (fs[n] && d < 0) puts("Yes");
    else puts("No");
  }

  return 0;
}
0