Submission #533820

#	Time	Username	Problem	Language	Result	Execution time	Memory
533820		RaresFelix	Crossing (JOI21_crossing)	C++17	100 / 100	1930 ms	191408 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define LT(x) ((x) == 'I' ? 2 : (x) == 'O')
#define CMB(x, y) ((x) == (y) ? (x) : (3 - (x) - (y)))
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define MN 257171
int n, q;
vector<int> C[10], P;
struct SL {
    vector<int> B;
    int V[4 * MN], E[4 * MN], L[4 * MN];
    void bd(int u, int s, int d) {
        L[u] = V[u] = E[u] = 0;
        if(s == d) {
            V[u] = B[s];
            E[u] = (B[s] == P[s]);
            return;
        }
        bd(u * 2, s, (s + d) / 2);
        bd(u * 2 + 1, (s + d) / 2 + 1, d);
        V[u] = ((V[u * 2] == V[u * 2 + 1]) ? V[u * 2] : -1);
        E[u] = E[u * 2] && E[u * 2 + 1];
    }
    SL(vector<int> E) : B(move(E)) { bd(1, 0, n-1); }
    void pp(int u, int s, int d) {
        if(!L[u]) return;
        int v = L[u] - 3;
        E[u] = (V[u] == v);
        if(s != d)
            L[u * 2] = L[u * 2 + 1] = L[u];
        L[u] = 0;
    }
    void pset(int l, int r, int v, int u, int s, int d) {
        pp(u, s, d);
        if(r < s || d < l) return;
        if(l <= s && d <= r) {
            L[u] = v + 3;
            pp(u, s, d);
            return;
        }
        pset(l, r, v, u * 2, s, (s + d) / 2);
        pset(l, r, v, u * 2 + 1, (s + d) / 2 + 1, d);
        V[u] = ((V[u * 2] == V[u * 2 + 1] )? V[u * 2] : -1);
        E[u] = E[u * 2] && E[u * 2 + 1];
    }
};
vector<SL> SS;
void af() {
    int ok = 0;
    for(auto &it : SS) ok |= it.E[1];
    cout << (ok ? "Yes\n" : "No\n");
}
void rd(vi &C) {
    string w;
    cin >> w;
    for(auto it : w) C.pb(LT(it));
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    char c;
    for(int i = 0; i < 3; ++i) rd(C[i]);
    int nr = 2;
    for(int i = 0; i < 3; ++i)
        for(int j = i + 1; j < 3; ++j)
            for(int k = !(++nr); k < n; ++k)
                C[nr].pb(c = CMB(C[i][k], C[j][k])), C[3 + nr].pb(CMB(c, C[3 - i - j][k]));
    cin >> q;
    rd(P);
    for(int i = 0; i < 9; ++i) SS.emplace_back(C[i]);
    af();
    for(int i = 1, l, r; i <= q; ++i) {
        cin >> l >> r >> c;
        --l, --r;
        for(auto &it : SS)
            it.pset(l, r, LT(c), 1, 0, n - 1);
        af();
    }
    return 0;
}

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