Submission #1212745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212745		Hamed_Ghaffari	Crossing (JOI21_crossing)	C++20	100 / 100	237 ms	12996 KiB

Main

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

#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)

const int MXN = 2e5 + 5;

int n, q;
string S[9], T;

inline void cross(int i, int j, int k) {
    S[k] = string(n, 'a');
    for(int x=0; x<n; x++)
        if(S[i][x]==S[j][x]) S[k][x] = S[i][x];
        else if(S[i][x]!='J' && S[j][x]!='J') S[k][x] = 'J';
        else if(S[i][x]!='O' && S[j][x]!='O') S[k][x] = 'O';
        else S[k][x] = 'I';
}

char lz[MXN<<2], ch[MXN<<2][9];
bool eq[MXN<<2][9];

inline void pull(int id) {
    for(int i=0; i<9; i++) {
        ch[id][i] = (ch[lc][i]==ch[rc][i]) ? ch[lc][i] : 'a';
        eq[id][i] = eq[lc][i] & eq[rc][i];
    }
}
inline void apply(char c, int id) {
    lz[id] = c;
    for(int i=0; i<9; i++)
        eq[id][i] = (ch[id][i]==c);
}
inline void push(int id) {
    if(lz[id]!='a') {
        apply(lz[id], lc);
        apply(lz[id], rc);
        lz[id] = 'a';
    }
}
void build(int l=0, int r=n, int id=1) {
    lz[id] = 'a';
    if(r-l==1) {
        for(int i=0; i<9; i++)
            eq[id][i] = ((ch[id][i]=S[i][l])==T[l]);
        return;
    }
    build(l, mid, lc);
    build(mid, r, rc);
    pull(id);
}
void upd(int s, int e, char c, int l=0, int r=n, int id=1) {
    if(s>=r || l>=e) return;
    if(s<=l && r<=e) {
        apply(c, id);
        return;
    }
    push(id);
    upd(s, e, c, l, mid, lc);
    upd(s, e, c, mid, r, rc);
    pull(id);
}
void print() {
    for(int i=0; i<9; i++)
        if(eq[1][i]) {
            cout << "Yes\n";
            return;
        }
    cout << "No\n";
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> S[0] >> S[1] >> S[2];
    cross(0, 1, 3);
    cross(0, 2, 4);
    cross(1, 2, 5);
    cross(2, 3, 6);
    cross(1, 4, 7);
    cross(0, 5, 8);
    cin >> q >> T;
    build();
    print();
    while(q--) {
        int l, r;
        char c;
        cin >> l >> r >> c;
        upd(l-1, r, c);
        print();
    }
    return 0;
}

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