Submission #1207991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207991		Boomyday	Crossing (JOI21_crossing)	C++20	100 / 100	1708 ms	20392 KiB

Main

//
// Created by adavy on 5/26/2025.
//

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int SSZ = 262144;
vector<int> seg(2*SSZ, 0);
vector<int> lz(2*SSZ, -1); // -1 means no flag
vector<int> flag(2*SSZ, -1); // -1 means fallacious flag
vector<int> curstring;
int N;
string start;

int conv(char c){
    if (c=='J') return 0;
    if (c=='O') return 1;
    if (c=='I') return 2;
    return -1; // should not happen
}

vector<int> sm(vector<int>& v1, vector<int>& v2, vector<int>& v3, int c1, int c2, int c3){
    vector<int> final;
    for(int i=0;i<v1.size();++i){
        final.push_back((v1[i]*c1 + v2[i]*c2 + v3[i]*c3) % 3);
    }
    return final;
}

void set_node(int rt, int tl, int tr){
    if (rt == 0){
        assert(0);
    }
    if (tl==tr && tl < N) {
        flag[rt] = curstring[tl];
        return;
    }
    if (tl == tr) return;
    int tm = (tl + tr) / 2;
    set_node(2*rt, tl, tm);
    set_node(2*rt + 1, tm + 1, tr);
    if (flag[2*rt] == flag[2*rt + 1]) flag[rt] = flag[2*rt];


}

void pushdown(int rt, int tl, int tr){
    if (lz[rt] == -1) return;
    seg[rt] = (lz[rt] == flag[rt]);
    if (tl != tr) {
        lz[2*rt] = lz[rt];
        lz[2*rt + 1] = lz[rt];
    }
    lz[rt] = -1;
}
void upd(int v, int l, int r, int rt, int tl, int tr){
    // out of bounds
    pushdown(rt, tl, tr);
    if (l > tr || r < tl) return;
    if (l <= tl && tr <= r) {
        lz[rt] = v;
        pushdown(rt, tl, tr);
        return;
    }

    int tm = (tl + tr) / 2;
    upd(v, l, r, 2*rt, tl, tm);
    upd(v, l, r, 2*rt + 1, tm + 1, tr);
    seg[rt] = seg[2*rt] & seg[2*rt + 1];
}

int query(int l, int r, int rt, int tl, int tr){
    pushdown(rt, tl, tr);
    if (l > tr || r < tl) return 1; // neutral element
    if (l <= tl && tr <= r) return seg[rt];

    int tm = (tl + tr) / 2;
    return query(l, r, 2*rt, tl, tm) & query(l, r, 2*rt + 1, tm + 1, tr);
}

void set_tree(vector<int>& vec){
    curstring = vec;
    seg.assign(2*SSZ, 0);
    lz.assign(2*SSZ, -1);
    flag.assign(2*SSZ, -1);
    set_node(1, 0, SSZ-1);
    // now set all nodes of the segment tree
    for(int i=0;i<N;++i){
        upd(conv(start[i]), i, i, 1, 0, SSZ-1);
    }
}

int main(){
    cin >> N;
    vector<vector<int>> s(3, vector<int>(N));
    vector<vector<int>> poss;
    for(int i=0;i<3;++i){
        string st; cin >> st;
        for(int j=0;j<N;++j){
            s[i][j] = conv(st[j]);
        }

    }

    poss.push_back(s[0]);
    poss.push_back(s[1]);
    poss.push_back(s[2]);
    poss.push_back(sm(s[0], s[1], s[2], 2,2,0));
    poss.push_back(sm(s[0], s[1], s[2], 2,0,2));
    poss.push_back(sm(s[0], s[1], s[2], 0,2,2));
    poss.push_back(sm(s[0], s[1], s[2], 2,1,1));
    poss.push_back(sm(s[0], s[1], s[2], 1,2,1));
    poss.push_back(sm(s[0], s[1], s[2], 1,1,2));

    int Q; cin >> Q;
    cin >> start;
    vector<pair<pair<int,int>,int>> qs(Q);
    for(int i=0;i<Q;++i){
        int l, r; char t; cin >> l >> r >> t;
        int type = conv(t);
        l--; r--;
        qs[i] = {{l,r}, type};
    }
    vector<bool> is_good(Q+1,0);

    for(auto& vec:poss){
        set_tree(vec);
        if (query(0, N-1, 1, 0, SSZ-1) == 1) {
            is_good[0] = 1;
        }
        for(int i=0;i<Q;++i){
            auto& [lr, type] = qs[i];
            upd(type, lr.first, lr.second, 1, 0, SSZ-1);
            if (query(0, N-1, 1, 0, SSZ-1) == 1) {
                is_good[i+1] = 1;
            }
        }

    }
    for(int i=0;i<=Q;++i){
        if (is_good[i]) cout << "Yes" << endl;
        else cout << "No" << endl;
    }


}

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