Submission #576031

#	Time	Username	Problem	Language	Result	Execution time	Memory
576031		dantoh000	Crossing (JOI21_crossing)	C++14	100 / 100	817 ms	33832 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int n,q;
string s[3];
string T;
long long pow5[200005];
long long one5[200005];
map<long long, int> m;
struct node{
    int s,e,m;
    long long v;
    int la;
    node *l, *r;
    node (int _s, int _e){
        s = _s, e = _e, m = (s+e)/2;
        v = la = 0;
        if (s != e){
            l = new node(s,m);
            r = new node(m+1,e);
            v = (l->v * pow5[e-m] + r->v)%mod;
        }
        else{
            v = (T[s-1] == 'J')?1:(T[s-1]=='O')?2:3;
        }
    }
    void prop(){
        if (la){
            v = (one5[e-s]*la)%mod;
            if (s != e){
                l->la = la;
                r->la = la;
            }
            la = 0;
        }

    }
    void up(int qs, int qe, int nv){
        prop();
        if (qs == s && qe == e){
            la = nv;
            return;
        }
        if (qs > m) r->up(qs,qe,nv);
        else if (qe <= m) l->up(qs,qe,nv);
        else {l->up(qs,m,nv), r->up(m+1,qe,nv);}
        l->prop(); r->prop();
        v = (l->v * pow5[e-m] + r->v)%mod;
    }

} *root;
long long hsh(string S){
    long long ret = 0;
    for (int i = 0; i < n; i++){
        int k = (S[i] == 'J')?1:(S[i]=='O')?2:3;
        ret = (ret*5 + k)%mod;
    }
    return ret;
}
string cross(string a, string b){
    string s = "";
    for (int i = 0; i < n; i++){
        if (a[i] == b[i]) s += a[i];
        else s += ('J' + 'O' + 'I') - a[i] - b[i];
    }
    return s;
}
void dfs(string x){
    int h = hsh(x);
    if (m[h] == 1) return;
    m[h] = 1;
    ///cout << x << endl;
    for (int i = 0; i < 3; i++){
        dfs(cross(x, s[i]));
    }
}
void gen(){
    dfs(s[0]);
    dfs(s[1]);
    dfs(s[2]);
}
int main(){
    cin >> n;
    pow5[0] = one5[0] = 1;
    for (int i = 1; i <= n; i++){
        pow5[i] = (pow5[i-1]*5)%mod;
        one5[i] = one5[i-1] + pow5[i];
    }
    cin >> s[0] >> s[1] >> s[2];
    gen();
    cin >> q;
    cin >> T;

    root = new node(1,n);
    int ans = m.count(root->v);
    if (ans > 0) cout << "Yes\n";
    else cout << "No\n";
    for (int i = 0; i < q; i++){
        int l,r;
        char c;
        cin >> l >> r >> c;
        root->up(l,r,(c == 'J')?1:(c=='O')?2:3);
        root->prop();
        int ans = m.count(root->v);
        if (ans > 0) cout << "Yes\n";
        else cout << "No\n";

    }



}

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