Submission #1055383

#TimeUsernameProblemLanguageResultExecution timeMemory
1055383YassirSalamaCrossing (JOI21_crossing)C++17
3 / 100
1709 ms126756 KiB
#include<bits/stdc++.h>
using namespace std;
map<char,__int128_t> mp;
#define all(v) v.begin(),v.end()
struct Hash {
    vector<__int128_t> v;
    __int128_t P,mod;
    const __int128_t maxn=2e5+100;
    __int128_t pref[(__int128_t)2e5+100];
    struct Node{
        __int128_t val;
        __int128_t lz;
        Node* left,*right;
        Node() : left(nullptr),right(nullptr){}
    };
    __int128_t f(__int128_t a){
        a%=mod;
        if(a<0) a+=mod;
        return a%=mod;
    }
    __int128_t sum(__int128_t l,__int128_t r){
        if(l==0) return pref[r];
        return f(pref[r]%mod-pref[l-1]%mod)%mod;
    }
    void push(Node* node,__int128_t l,__int128_t 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,__int128_t l,__int128_t r){
        push(node,l,r);
        __int128_t mid=(l+r)/2;
        if(l==r) return;
        push(node->left,l,mid);
        push(node->right,mid+1,r);
    }
    void build(Node* node,__int128_t l,__int128_t r,vector<__int128_t> &v){
        if(l==r){
            node->val=v[l];
            return;
        }
        __int128_t 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,__int128_t l,__int128_t r,__int128_t ql,__int128_t qr,__int128_t x){
        p(node,l,r);
        if(ql<=l&&r<=qr){
            node->lz=x;p(node,l,r);
            return;
        }
        __int128_t 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;
    }
    __int128_t query(Node* node,__int128_t l,__int128_t r,__int128_t ql,__int128_t qr){
        if(ql<=l&&r<=qr) return node->val%mod;
        __int128_t mid=(l+r)/2;
        __int128_t 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<__int128_t> hsh(string s){
        __int128_t n=s.length();
        __int128_t c=1;
        vector<__int128_t> v(n);
        for(__int128_t i=0;i<n;i++){
            __int128_t x=mp[s[i]];
            v[i]=(x*c%mod)%mod;
            c=(c*P%mod)%mod;
        }
        return v;
    }
    Node* root;
    void b(string s,__int128_t p,__int128_t MOD){
        P=p;
        mod=MOD;
        v=hsh(s);
        for(__int128_t i=0;i<maxn;i++){
            pref[i]=binpow(P,i);
            if(i){
                pref[i]=f(pref[i]+pref[i-1]%mod)%mod;
            }
        }
        root=new Node();
        __int128_t n=s.size();
        build(root,0,n-1,v);
    }
    __int128_t get(){
        return root->val;
    }
    __int128_t binpow(__int128_t a,__int128_t b){
        __int128_t res=1;
        while(b){
            if(b&1) {
                res=(res*a%mod)%mod;
            }
            a=(a*a%mod)%mod;
            b>>=1;
        }
        return res;
    }
};
int main(){
    mp['J']=1;mp['O']=4;mp['I']=7;
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;
    cin>>n;
    string s;
    cin>>s>>s>>s;
    int q;
    cin>>q;
    string t;
    cin>>t;
    Hash a1;a1.b(s,31,1e9+7);
    Hash b1;b1.b(t,31,1e9+7);
    Hash a2;a2.b(s,41,1e9+3);
    Hash b2;b2.b(t,41,1e9+3);

    puts((a1.get()==b1.get()&&a2.get()==b2.get())?"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((a1.get()==b1.get()&&a2.get()==b2.get())?"Yes":"No");
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...