Submission #895236

#	Time	Username	Problem	Language	Result	Execution time	Memory
895236		Alcabel	Crossing (JOI21_crossing)	C++17	100 / 100	1409 ms	17816 KiB

Main

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

struct SegTree {
    int n, N;
    vector<char> sym, lazy;
    vector<bool> same;
    SegTree() {}
    SegTree(int _n, const string& s) {
        n = _n, N = 1;
        while (N < n) {
            N <<= 1;
        }
        sym.resize(2 * N, -2);
        same.resize(2 * N, true);
        lazy.resize(2 * N, -1);
        for (int i = 0; i < n; ++i) {
            sym[N + i] = s[i];
            // cerr << "v: " << N + i << ", sym: " << st[N + i].sym << '\n';
        }
        for (int i = N - 1; i > 0; --i) {
            if (sym[2 * i] == -2) {
                sym[i] = sym[2 * i + 1];
            } else if (sym[2 * i + 1] == -2) {
                sym[i] = sym[2 * i];
            } else {
                if (sym[2 * i] == -1 || sym[2 * i + 1] == -1 || sym[2 * i] != sym[2 * i + 1]) {
                    sym[i] = -1;
                } else {
                    sym[i] = sym[2 * i];
                }
            }
            // cerr << "v: " << i << ", sym: " << st[i].sym << '\n';
        }
    }
    void push(int v) {
        // cerr << "v: " << v << ", lazy: " << lazy[v] << ' ';
        if (sym[v] == lazy[v]) {
            same[v] = true;
        } else {
            same[v] = 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);
        same[v] = same[2 * v] && same[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 same[1];
    }
    ~SegTree() {}
};

void solve() {
    int n;
    cin >> n;
    vector<string> s(3);
    for (int i = 0; i < 3; ++i) {
        cin >> s[i];
    }
    for (int i = 0; i < 2; ++i) {
        for (int j = i + 1; j < 3; ++j) {
            s.emplace_back(string(n, '.'));
            for (int pos = 0; pos < n; ++pos) {
                if (s[i][pos] == s[j][pos]) {
                    s.back()[pos] = s[j][pos];
                } else {
                    s.back()[pos] = 'J' + 'O' + 'I' - s[i][pos] - s[j][pos];
                }
            }
            int k = 3 - i - j;
            s.emplace_back(string(n, '.'));
            for (int pos = 0; pos < n; ++pos) {
                if (s[(int)s.size() - 2][pos] == s[k][pos]) {
                    s.back()[pos] = s[k][pos];
                } else {
                    s.back()[pos] = 'J' + 'O' + 'I' - s[(int)s.size() - 2][pos] - s[k][pos];
                }
            }
        }
    }
    int q;
    cin >> q;
    string t;
    cin >> t;
    vector<SegTree> st(9);
    for (int i = 0; i < 9; ++i) {
        st[i] = SegTree(n, s[i]);
        for (int pos = 0; pos < n; ++pos) {
            st[i].assign(pos, pos + 1, t[pos]);
        }
    }
    auto query = [&]() -> bool {
        for (int i = 0; i < 9; ++i) {
            if (st[i].query()) {
                return true;
            }
        }
        return false;
    };
    if (query()) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
    while (q--) {
        int l, r;
        char c;
        cin >> l >> r >> c;
        --l;
        for (int i = 0; i < 9; ++i) {
            st[i].assign(l, r, c);
        }
        if (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: 23 / 23
• Subtask 4: 51 / 51