Submission #1370374

#TimeUsernameProblemLanguageResultExecution timeMemory
1370374hovuviettruongCrossing (JOI21_crossing)C++20
100 / 100
169 ms25136 KiB
#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
#define pii pair<int,int>
#define el '\n'
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define N 200006
using namespace std;
const int mod = 1e9 + 7;
const int base = 37;

string s[4];
int H[N];
int ht[N];
int p[N];
int hc[4][N];
pii st[N << 2];
int lazy[N << 2];

int geth(int l, int r, int h[]){
    return (h[r] - h[l - 1]*p[r - l + 1]%mod + mod)%mod;
}

void push(int id, int l, int r){
    if (lazy[id]  == -1) return;
    int m = (l + r)/2;
    st[id << 1].fi = hc[lazy[id]][m - l + 1];
    st[id << 1 | 1].fi = hc[lazy[id]][r - m];
    st[id << 1].se = m - l + 1;
    st[id << 1 | 1].se = r - m;
    lazy[id << 1] = lazy[id << 1 | 1] = lazy[id];
    lazy[id] = -1;
}
void update(int id, int l, int r, int u, int v, int k){
    if (l > v || r < u) return;
    if (u <= l && r <= v){
        st[id].fi = hc[k][r - l + 1];
        st[id].se = r - l + 1;
        lazy[id] = k;
        return;
    }
    push(id, l, r);
    int m = (l + r)/2;
    update(id << 1, l, m, u, v, k);
    update(id << 1 | 1, m + 1, r, u, v, k);
    st[id].fi = (st[id << 1].fi*p[r - m]%mod + st[id << 1 | 1].fi) % mod;
    st[id].se = r - l + 1;

}
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    p[0] = 1;
    for (int i = 1; i <= n + 1; i++) p[i] = p[i - 1] * base % mod;

    for (int i = 1; i <= 3; i++) {
        cin >> s[i];
        s[i] = ' ' + s[i];
        for (int j = 1; j <= n; j++) H[i] = (H[i]*base + s[i][j] - 'A' + 1) % mod;
    }
    int cnt = 3;

    vector<string> v;
    for (int i = 1; i < 3; i++){
        for (int j = i + 1; j <= 3; j++){
            string b = " ";
            ++cnt;
            for (int k = 1; k <= n; k++){
                if (s[i][k] == s[j][k]) b += s[i][k];
                else if ( (s[j][k] == 'J' && s[i][k] == 'O') || (s[j][k] == 'O' && s[i][k] == 'J')) b += 'I';
                else if ((s[j][k] == 'J' && s[i][k] == 'I') || (s[j][k] == 'I' && s[i][k] == 'J')) b += 'O';
                else b += 'J';
                H[cnt] = (H[cnt]*base + b[k] - 'A' + 1) % mod;
            }
            v.push_back(b);
        }
    }

    int i = 3;
    for (string st : v){
            string b = " ";
            ++cnt;
            for (int k = 1; k <= n; k++){
                if (st[k] == s[i][k]) b += s[i][k];
                else if ( (st[k] == 'J' && s[i][k] == 'O') || (st[k] == 'O' && s[i][k] == 'J')) b += 'I';
                else if ((st[k] == 'J' && s[i][k] == 'I') || (st[k] == 'I' && s[i][k] == 'J')) b += 'O';
                else b += 'J';
                H[cnt] = (H[cnt]*base + b[k] - 'A' + 1) % mod;
            }
        --i;
    }
    
    memset(lazy, -1, sizeof lazy);
     for (int i = 1; i <= n; i++){
        hc[0][i] = (hc[0][i - 1]*base + 'J' - 'A' + 1) % mod;
        hc[1][i] = (hc[1][i - 1]*base + 'O' - 'A' + 1) % mod;
        hc[2][i] = (hc[2][i - 1]*base + 'I' - 'A' + 1) % mod;
    }

    int q; cin >> q;
    string t;
    cin >> t;
    t = ' ' + t;
    for (int i = 1; i <= n; i++){
        ht[i] = (ht[i - 1]*base + t[i] - 'A' + 1)%mod;
        if (t[i] == 'J') update(1, 1, n, i, i, 0);
        else if (t[i] == 'O') update(1, 1, n, i, i, 1);
        else update(1, 1, n, i, i, 2);
    }
 
    int ok = 0;
    for (int i = 1; i <= cnt; i++){
        if (H[i] == ht[n]) {
            ok = 1;
            break;
        }
    }
    if (ok) cout << "Yes\n";
    else cout << "No\n";
   

    while(q--){
        int l, r; char c;
        cin >> l >> r >> c;
        int d = 0;
        if (c == 'O') d = 1;
        if (c == 'I') d = 2;
        update(1, 1, n, l, r, d);
        ok = 0;
        //cout <<  st[1].fi << '\n';
        for (int i = 1; i <= cnt; i++){
            if (st[1].fi == H[i]) {
                ok = 1;
                cout << "Yes\n";
                break;
            }
        }
        if (!ok) cout << "No\n";


    }

    

    
    

   






}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...