Submission #1245582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245582		slivajan	Crossing (JOI21_crossing)	C++20	26 / 100	171 ms	6064 KiB

Main

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

using un = long long;
using vuc = vector<un>;
using vol = vector<bool>;

#define REP(i, a, b) for (un i = (un)a ; i < (un)b; i++)
#define FEAC(i, a) for (auto&& i : a)
#define vec vector
#define ALL(x) (x).begin(), (x).end()


enum Gen {
    NONE = 0,
    A, B, C
};

Gen char2Gen(char c) {
    if (c == 'J') return A;
    if (c == 'O') return B;
    if (c == 'I') return C;

    return NONE;
}


struct iv_tree {

    vec<Gen> lenost;
    vec<Gen> vzor;
    vol tree;
    un N;


    iv_tree(string start, string target){
        N = start.size();
        while(N&(N-1)) N++;

        tree = vol(2*N, true);
        vzor = vec<Gen>(2*N, NONE);
        lenost = vec<Gen>(2*N, NONE);

        REP(i, 0, start.size()){
            tree[N+i] = (start[i] == target[i]);
            vzor[N+i] = char2Gen(target[i]);
        }

        for (un i = N-1; i>0; i--){
            tree[i] = tree[2*i] and tree[2*i + 1];

            if (vzor[2*i] == vzor[2*i + 1]) vzor[i] = vzor[2*i];
            else vzor[i] = NONE;
        }
    }

    string getStatus() {
        processLenost(1);
        if (tree[1]) return "Yes";
        else return "No";
    }

    void processLenost(un v){
        if (lenost[v] == NONE) return;

        if (lenost[v] == vzor[v]) tree[v] = true;
        else tree[v] = false;

        if (v < N){
            lenost[2*v] = lenost[v];
            lenost[2*v+1] = lenost[v];
        }

        lenost[v] = NONE;
        return;
    }

    void update(Gen val, un L, un R){
        updateRec(val, L, R, 1, 0, N-1);
    }

    void updateRec(Gen val, un L, un R, un v, un vL, un vR){
        processLenost(v);
        
        if ((vR < L) or (R < vL)){
            return;
        }

        if ((L <= vL) and (vR <= R)) {
            lenost[v] = val;
            processLenost(v);
            return;
        }

        
        un vM = (vL+vR)/2;

        updateRec(val, L, R, 2*v, vL, vM);
        updateRec(val, L, R, 2*v+1, vM+1, vR);

        tree[v] = tree[2*v] and tree[2*v+1];
        return;
    }

};



int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    un N; cin >> N;

    string target; cin >> target;

    string trash;
    cin >> trash >> trash;

    un Q; cin >> Q;
    string start; cin >> start;

    iv_tree IV(start, target);

    cout << IV.getStatus() << "\n";

    REP(q, 0, Q){
        un L, R; cin >> L >> R;
        char c; cin >> c;
        L--; R--;

        IV.update(char2Gen(c), L, R);
        cout << IV.getStatus() << "\n";

    }


}

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