Submission #1055433

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055433		YassirSalama	Crossing (JOI21_crossing)	C++17	100 / 100	1841 ms	447060 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
map<char,int> mp;
#define all(v) v.begin(),v.end()
struct Hash {
    vector<int> v;
    int P,mod;
    const int maxn=2e5+100;
    int pref[(int)2e5+100];
    struct Node{
        int val;
        int lz;
        Node* left,*right;
        Node() : left(nullptr),right(nullptr){}
    };
    int f(int a){
        a%=mod;
        if(a<0) a+=mod;
        return a%=mod;
    }
    int sum(int l,int r){
        if(l==0) return pref[r];
        return f(pref[r]%mod-pref[l-1]%mod)%mod;
    }
    void push(Node* node,int l,int r){
        if(node->lz==0) return;
        node->val=f(node->lz*f(sum(l,r))%mod);
        if(l!=r){
            node->left->lz=node->lz;
            node->right->lz=node->lz;
        }
        node->lz=0;
    }
    void p(Node* node,int l,int r){
        push(node,l,r);
        int mid=(l+r)/2;
        if(l==r) return;
        push(node->left,l,mid);
        push(node->right,mid+1,r);
    }
    void build(Node* node,int l,int r,vector<int> &v){
        node->lz=0;
        if(l==r){
            node->val=v[l];
            return;
        }
        int mid=(l+r)/2;
        node->left=new Node();
        node->right=new Node();
        build(node->left,l,mid,v);
        build(node->right,mid+1,r,v);
        node->val=((node->left->val%mod)+(node->right->val%mod))%mod;
    }
    void update(Node* node,int l,int r,int ql,int qr,int x){
        p(node,l,r);
        if(ql<=l&&r<=qr){
            node->lz=x;p(node,l,r);
            return;
        }
        int mid=(l+r)>>1;
        if(ql<=mid){
            update(node->left,l,mid,ql,qr,x);
        }
        if(qr>mid) update(node->right,mid+1,r,ql,qr,x);
        node->val=((node->left->val%mod)+(node->right->val%mod))%mod;
    }
    int query(Node* node,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr) return node->val%mod;
        int mid=(l+r)/2;
        int ans=0;
        if(ql<=mid) ans=f(ans+query(node->left,l,mid,ql,qr)),ans%=mod;
        if(qr>mid) ans=f(ans+query(node->right,mid+1,r,ql,qr)),ans%=mod;
        return ans%mod;
    }
    vector<int> hsh(string s){
        int n=s.length();
        int c=1;
        vector<int> v(n);
        for(int i=0;i<n;i++){
            int x=mp[s[i]];
            v[i]=(x%mod*c%mod)%mod;
            c=(c%mod*P%mod)%mod;
        }
        return v;
    }
    Node* root;
    void b(string s,int p,int MOD){
        P=p;
        mod=MOD;
        v=hsh(s);
        for(int i=0;i<maxn;i++){
            pref[i]=binpow(P,i)%mod;
            if(i){
                pref[i]=f(pref[i]%mod+pref[i-1]%mod)%mod;
            }
        }
        root=new Node();
        int n=s.size();
        build(root,0,n-1,v);
    }
    int get(){
        return root->val%mod;
    }
    int binpow(int a,int b){
        int res=1;
        while(b){
            if(b&1) {
                res=(res%mod*a%mod)%mod;
            }
            a=(a%mod*a%mod)%mod;
            b>>=1;
        }
        return res;
    }
};
Hash b1,b2;
Hash a[9],b[9];

signed main(){
    mp['J']=1;mp['O']=4;mp['I']=7;
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;
    cin>>n;
    vector<string> v(3);
    cin>>v[0]>>v[1]>>v[2];
    auto cross = [&](string a,string b){
        string s;
        for(int i=0;i<n;i++){
            if(a[i]==b[i]) s+=a[i];
            else{
                for(auto c:"JOI")
                    if(c!=a[i]&&c!=b[i]){
                        s+=c;
                        break;
                    }
            }
        }
        return s;
    };
    set<string> s(v.begin(),v.end());
    while(true){
        bool f=false;
        set<string> ss=s;
        for(auto x:s){
            for(auto y:s){
                string t=cross(x,y);
                if(s.count(t)) continue;
                ss.insert(t);f=true;
            }
        }
        s=ss;
        if(!f) break;
    }
    v.clear();
    for(auto x:s) v.push_back(x);
    int q;
    cin>>q;
    string t;
    cin>>t;
    b1.b(t,31,1e9+7);
    b2.b(t,41,1e9+3);
    int c=v.size();
    for(int i=0;i<c;i++){
        a[i].b(v[i],31,1e9+7);
        b[i].b(v[i],41,1e9+3);
    }
    auto check = [&](){
        bool ok=true;
        for(int i=0;i<c;i++){
            if(a[i].get()==b1.get()&&b[i].get()==b2.get()) return true;
        }
        return false;
    };
    puts(check()?"Yes":"No");
    while(q--){
        int l,r;
        cin>>l>>r;
        l--,r--;
        char c;
        cin>>c;
        b1.update(b1.root,0,n-1,l,r,mp[c]);
        b2.update(b2.root,0,n-1,l,r,mp[c]);
        puts(check()?"Yes":"No");
    }
}

Compilation message (stderr)

Main.cpp: In lambda function:
Main.cpp:169:14: warning: unused variable 'ok' [-Wunused-variable]
  169 |         bool ok=true;
      |              ^~

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