Submission #1055360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055360		YassirSalama	Crossing (JOI21_crossing)	C++17	3 / 100	7059 ms	5176 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7,P=31;
map<char,int> mp;
int binpow(int a,int b){
    int res=1;
    while(b){
        if(b&1) {
            res=(res*a%mod)%mod;
        }
        a=(a*a%mod)%mod;
        b>>=1;
    }
    return res;
}
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*c%mod)%mod;
        c=(c*P%mod)%mod;
    }
    return v;
}
#define all(v) v.begin(),v.end()
signed main(){mp['J']=1;mp['O']=2;mp['I']=3;
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;
    vector<int> a=hsh(s);
    vector<int> b=hsh(t);
    int sum=0;
    int ans=0;
    for(auto x:a){
        ans+=x;
        ans%=mod;
    }
    for(auto x:b) {
        sum+=x;
        sum%=mod;
    }
    puts(ans==sum?"Yes":"No");
    while(q--){
        int l,r;
        cin>>l>>r;
        l--,r--;
        char c;
        cin>>c;
        for(int i=l;i<=r;i++){
            sum-=b[i];
            sum%=mod;
            if(sum<0) sum+=mod;
            sum%=mod;
            b[i]=(mp[c]*binpow(P,i)%mod)%mod;
            sum+=b[i];
            sum%=mod;
            if(sum<0) sum+=mod;
            sum%=mod;
        }
        if(ans==sum){
            puts("Yes");
        }else puts("No");
    }
}

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