Submission #1055396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055396		YassirSalama	Crossing (JOI21_crossing)	C++17	26 / 100	1041 ms	136836 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 a1,a2,a3,b1,b2,b3;
signed 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;
    a1.b(s,31,1e9+7);
    b1.b(t,31,1e9+7);
    a2.b(s,41,1e9+3);
    b2.b(t,41,1e9+3);
    a3.b(s,13,1000000009);
    b3.b(s,13,1000000009);
    puts((a1.get()==b1.get()&&a2.get()==b2.get()&&a3.get()==b3.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()&&a3.get()==b3.get())?"Yes":"No");
    }
}

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