Submission #1216667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216667		Younis_Dwai	Crossing (JOI21_crossing)	C++20	26 / 100	134 ms	9484 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 s,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],H=0;
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]);
     for(int i=1;i<=n;i++) H=Add(H,Mul(s[i]-'A',P[i]));
     build(1,1,n);
     return ;
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>s>>s>>s;
    s='!'+s;
    int q;cin>>q;
    cin>>T;
    T='!'+T;
    init();
    cout<<(T==s ? "Yes"  :"No")<<endl;
    while(q--){
          int l,r;char c;
          cin>>l>>r>>c;
          upd(1,1,n,l,r,c);
          if(tree[1]==H) cout<<"Yes"<<endl;
          else cout<<"No"<<endl;
    }
    return 0;
}

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