Submission #1216907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216907		Younis_Dwai	Crossing (JOI21_crossing)	C++20	100 / 100	1678 ms	12872 KiB

Main

//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#define int long long
#define F first
#define S second
#define pb push_back
#define popp pop_back
#define in insert
#define endl "\n"
#define mid (l+r)/2
using namespace std;
const int N=2e5+5;
const int M=1e9+7;
mt19937 rnd(time(0));
string s1,s2,s3,T;
int Add(int x , int y){
    x+=y;
    if(x>=M) x-=M;
    return x;
}
int Mul(int x , int y){
    x*=y;
    return x%M;
}
int Sub(int x  ,int y){
    x-=y;
    if(x<0) x+=M;
    return x;
}
int n,tree[N*4],p=rnd(),P[N],pref[N];
char lz[N*4];
void build(int node , int l , int r){
     lz[node]='!';
     if(l==r){
        tree[node]=Mul(P[l],T[l]-'A');
        return ;
     }
     build(node*2,l,mid);
     build(node*2+1,mid+1,r);
     tree[node]=Add(tree[node*2],tree[node*2+1]);
     return ;
}
void Val(int node , int l , int r , char c){
     tree[node]=Mul(c-'A',Sub(pref[r],pref[l-1]));
     return ;
}
void push(int node , int l , int r){
     if(lz[node]=='!') return ;
     lz[node*2]=lz[node*2+1]=lz[node];
     Val(node*2,l,mid,lz[node]);
     Val(node*2+1,mid+1,r,lz[node]);
     lz[node]='!';
     return ;
}
void upd(int node , int l , int r  ,int s , int e  , char c){
     if(l>e || r<s) return ;
     else if(l>=s && r<=e){
          lz[node]=c;
          Val(node,l,r,c);
          return ;
     }
     else{
        push(node,l,r);
        upd(node*2,l,mid,s,e,c);
        upd(node*2+1,mid+1,r,s,e,c);
        tree[node]=Add(tree[node*2],tree[node*2+1]);
     }
     return ;
}
void init(){
     P[0]=1;
     for(int i=1;i<N;i++) P[i]=Mul(P[i-1],p);
     for(int i=1;i<N;i++) pref[i]=Add(pref[i-1],P[i]);
     build(1,1,n);
     return ;
}
int Hash(string x){
    int H=0;
    for(int i=1;i<x.size();i++){
        H=Add(H,Mul(x[i]-'A',P[i]));
    }
    return H;
}
set<int> s;
string cross(string x , string y){
     string ret="";
     for(int i=0;i<x.size();i++){
         if(x[i]==y[i]) ret.pb(x[i]);
         else{
            ret.pb('J'+'O'+'I'-x[i]-y[i]);
         }
     }
     return ret ;
}
void generate_(string cur , int id){
     if(id==6){
        s.in(Hash(cur));
        return ;
     }
     generate_(cross(cur,s1),id+1);
     generate_(cross(cur,s2),id+1);
     generate_(cross(cur,s3),id+1);
     return ;
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>s1>>s2>>s3;

    s1='!'+s1;
    s2='!'+s2;
    s3='!'+s3;
    int q;cin>>q;
    cin>>T;
    T='!'+T;
    init();
    generate_(s1,1);
    generate_(s2,1);
    generate_(s3,1);
    cout<<(s.find(tree[1])!=s.end() ? "Yes"  :"No")<<endl;
    while(q--){
          int l,r;char c;
          cin>>l>>r>>c;
          upd(1,1,n,l,r,c);
          if(s.find(tree[1])!=s.end()) 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