Submission #661760

#	Time	Username	Problem	Language	Result	Execution time	Memory
661760		Darren0724	Crossing (JOI21_crossing)	C++17	100 / 100	686 ms	31636 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(),x.end()
const int INF=1e18;
int k=29;
const int mod=1e9+7;
vector<int> pw;
vector<int> pw1;
struct seg{
    int l,m,r,lz=0,val=0;
    seg *lc,*rc;
    seg(int l1,int r1){
        l=l1,r=r1;
        m=(l+r)>>1;
        if(r-l==1){
            return;
        }
        lc=new seg(l,m);
        rc=new seg(m,r);
    }
    int rv(){
        if(lz!=0){
            return lz*pw1[r-l-1]%mod;
        }
        return val;
    }
    void pull(){
        val=lc->rv()+rc->rv()*pw[m-l];
        val%=mod;
    }
    void push(){
        if(lz!=0){
            lc->lz=lz;
            rc->lz=lz;
            lz=0;
        }
    }
    void upd(int a,int b,int p){
        if(a<=l&&b>=r){
            lz=p;
            return;
        }
        push();
        if(a<m){
            lc->upd(a,b,p);
        }
        if(b>m){
            rc->upd(a,b,p);
        }
        pull();
    }
};
string comb(string &a,string &b){
    int n=a.size();
    string ans="";
    for(int i=0;i<n;i++){
        if(a[i]==b[i]){
            ans+=a[i];
        }
        else{
            if(a[i]!='J'&&b[i]!='J'){
                ans+='J';
            }
            if(a[i]!='O'&&b[i]!='O'){
                ans+='O';
            }
            if(a[i]!='I'&&b[i]!='I'){
                ans+='I';
            }
        }
    }
    return ans;
}
int get_hash(string &s){
    int ans=0;
    int n=s.size();
    for(int i=n-1;i>=0;i--){
        ans=ans*k+s[i]-'A';
        ans%=mod;
    }
    return ans;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    pw.resize(n+1);
    pw1.resize(n+1);
    pw[0]=1;
    pw1[0]=1;
    for(int i=1;i<=n;i++){
        pw[i]=(pw[i-1]*k)%mod;
        pw1[i]=pw1[i-1]+pw[i];
        pw1[i]%=mod;
    }
    vector<string> s(9);
    vector<int> v(9);
    for(int i=0;i<3;i++){
        cin>>s[i];
    }
    s[3]=comb(s[0],s[1]);
    s[4]=comb(s[0],s[2]);
    s[5]=comb(s[1],s[2]);
    s[6]=comb(s[5],s[0]);
    s[7]=comb(s[4],s[1]);
    s[8]=comb(s[3],s[2]);
    for(int i=0;i<9;i++){
        v[i]=get_hash(s[i]);
    }
    int q;cin>>q;
    string str;cin>>str;
    seg *rt=new seg(0,n);
    for(int i=0;i<n;i++){
        rt->upd(i,i+1,str[i]-'A');
    }
    int ans=rt->rv();
    bool flag=0;
    for(int j=0;j<9;j++){
        if(ans==v[j]){
            flag=1;
        }
    }
    if(flag){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
    for(int i=0;i<q;i++){
        int a,b;cin>>a>>b;
        char c;cin>>c;
        rt->upd(a-1,b,c-'A');
        int ans=rt->rv();
        bool flag=0;
        for(int j=0;j<9;j++){
            if(ans==v[j]){
                flag=1;
            }
        }
        if(flag){
            cout<<"Yes"<<endl;
        }
        else{
            cout<<"No"<<endl;
        }
    }


    return 0;
}

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