Submission #70245646

---

Source Code Expand

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;

#define int long long
#define ALL(x) (x).begin(), (x).end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

typedef pair<int, int> PI;
typedef pair<int, pair<int, int>> PII;
static const int INF = 1010000000000000017LL;
static const double eps = 1e-12;
static const double pi = 3.14159265358979323846;
static const int dx[4] = {1, -1, 0, 0};
static const int dy[4] = {0, 0, 1, -1};
static const int ddx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
static const int ddy[8] = {0, 0, 1, -1, 1, -1, 1, -1};

template <class T>
inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

int Q;

signed main() {
    cin >> Q;
    string S = "";
    int b = 0;
    int mi;

    vector<int> A(Q, 0);
    auto op = [](int a, int b) { return min(a, b); };
    auto e = []() { return INF; };
    segtree<int, op, e> seg(A);

    while (Q--) {
        int q;
        cin >> q;
        if (q == 1) {
            char c;
            cin >> c;
            if (c == '(') {
                b++;
            } else {
                b--;
            }
            S.push_back(c);
            int k = S.size();
            seg.set(k - 1, b);
            mi = seg.prod(0, k);
        } else {
            if (S[S.size() - 1] == '(') {
                b--;
            } else {
                b++;
            }
            S.pop_back();

            int k = S.size();

            if (k == 0) {
                mi = 0;
            } else {
                seg.set(k - 1, b);
                mi = seg.prod(0, k);
            }
        }
        if (b == 0 && mi == 0) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
}

Submission Info

Judge Result