제출 #894953

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
894953		Alcabel	Crossing (JOI21_crossing)	C++17	26 / 100	191 ms	7000 KiB

Main

#include <bits/stdc++.h>
using namespace std;

struct Cell {
    char sym;
    bool same;
    Cell() { sym = -2, same = true; }
    Cell operator+(const Cell& other) const {
        if (sym == -2) {
            return other;
        }
        if (other.sym == -2) {
            return *this;
        }
        Cell res;
        if (sym == -1 || other.sym == -1 || sym != other.sym) {
            res.sym = -1;
        } else {
            res.sym = sym;
        }
        res.same = same && other.same;
        return res;
    }
    ~Cell() {}
};

struct SegTree {
    int n, N;
    vector<char> lazy;
    vector<Cell> st;
    SegTree() {}
    SegTree(int _n, const string& s) {
        n = _n, N = 1;
        while (N < n) {
            N <<= 1;
        }
        st.resize(2 * N);
        lazy.resize(2 * N, -1);
        for (int i = 0; i < n; ++i) {
            st[N + i].sym = s[i];
            // cerr << "v: " << N + i << ", sym: " << st[N + i].sym << '\n';
        }
        for (int i = N - 1; i > 0; --i) {
            st[i] = st[2 * i] + st[2 * i + 1];
            // cerr << "v: " << i << ", sym: " << st[i].sym << '\n';
        }
    }
    void push(int v) {
        // cerr << "v: " << v << ", lazy: " << lazy[v] << ' ';
        if (st[v].sym == lazy[v]) {
            st[v].same = true;
        } else {
            st[v].same = false;
        }
        // cerr << "same: " << st[v].same << '\n';
        if (v < N) {
            lazy[2 * v] = lazy[v];
            lazy[2 * v + 1] = lazy[v];
        }
        lazy[v] = -1;
    }
    void assign(int v, int tl, int tr, int l, int r, char c) {
        if (lazy[v] != -1) {
            push(v);
        }
        if (tl >= r || tr <= l) {
            return;
        }
        if (l <= tl && tr <= r) {
            lazy[v] = c;
            push(v);
            return;
        }
        int m = tl + (tr - tl) / 2;
        assign(2 * v, tl, m, l, r, c);
        assign(2 * v + 1, m, tr, l, r, c);
        st[v] = st[2 * v] + st[2 * v + 1];
        // cerr << "v: " << v << ", same: " << st[v].same << '\n';
    }
    void assign(int l, int r, char c) {
        assign(1, 0, N, l, r, c);
    }
    bool query() {
        if (lazy[1] != -1) {
            push(1);
        }
        return st[1].same;
    }
    ~SegTree() {}
};

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s >> s >> s;
    int q;
    cin >> q;
    string t;
    cin >> t;
    SegTree st(n, s);
    for (int i = 0; i < n; ++i) {
        st.assign(i, i + 1, t[i]);
    }
    if (st.query()) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
    while (q--) {
        int l, r;
        char c;
        cin >> l >> r >> c;
        --l;
        st.assign(l, r, c);
        if (st.query()) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif

    return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 23 / 23
• Subtask 3: 0 / 23
• Subtask 4: 0 / 51