Submission #507609

#TimeUsernameProblemLanguageResultExecution timeMemory
507609nichkeCrossing (JOI21_crossing)C++14
26 / 100
350 ms17668 KiB
// I may fail a thousand times // But there is no giving up // IOI - here I come #include <bits/stdc++.h> #define int long long using namespace std; const int BASE1=271; const int BASE2=487; const int MOD1=10000223; const int MOD2=62528561; string s; map<char,int> mp; int lazy[(int)8e5+5]; int tree[(int)8e5+5][2]; int pref[(int)2e5+5][2]; string calc(string x,string y){ string ret=""; int sz=(int)x.length(); for(int i=0;i<sz;i++){ if(x[i]==y[i])ret+=x[i]; else{ char a=x[i]; char b=y[i]; if(a>b)swap(a,b); if(a=='I'&&b=='J')ret+='O'; if(a=='I'&&b=='O')ret+='J'; if(a=='J'&&b=='O')ret+='I'; } } return ret; } int mul(int a,int b,int MOD){ int ret=(a*b)%MOD; if(ret<0)ret+=MOD; return ret; } int add(int a,int b,int MOD){ int ret=(a+b)%MOD; if(ret<0)ret+=MOD; return ret; } void build(int v,int l,int r){ if(l==r){ tree[v][0]=mul(mp[s[l-1]],add(pref[r][0],-pref[l-1][0],MOD1),MOD1); tree[v][1]=mul(mp[s[l-1]],add(pref[r][1],-pref[l-1][1],MOD2),MOD2); return; } int m=(l+r)/2; build(2*v,l,m); build(2*v+1,m+1,r); tree[v][0]=add(tree[2*v][0],tree[2*v+1][0],MOD1); tree[v][1]=add(tree[2*v][1],tree[2*v+1][1],MOD2); } void push(int v,int l,int r){ if(l>r)return; if(lazy[v]!=-1){ if(l!=r){ lazy[2*v]=lazy[v]; lazy[2*v+1]=lazy[v]; } tree[v][0]=mul(lazy[v],add(pref[r][0],-pref[l-1][0],MOD1),MOD1); tree[v][1]=mul(lazy[v],add(pref[r][1],-pref[l-1][1],MOD2),MOD2); lazy[v]=-1; } } void upd(int v,int l,int r,int ul,int ur,int t){ push(v,l,r); if(l>r||ul>ur||l>ur||r<ul)return; if(l>=ul&&r<=ur){ lazy[v]=t; push(v,l,r); return; } int m=(l+r)/2; upd(2*v,l,m,ul,ur,t); upd(2*v+1,m+1,r,ul,ur,t); tree[v][0]=add(tree[2*v][0],tree[2*v+1][0],MOD1); tree[v][1]=add(tree[2*v][1],tree[2*v+1][1],MOD2); } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n;cin>>n; mp['I']=0; mp['J']=1; mp['O']=2; vector<string> v(3); for(int i=0;i<3;i++)cin>>v[i]; queue<string> q; for(int i=0;i<3;i++)q.push(v[i]); v.clear(); map<string,int> vis; for(;!q.empty();){ string x=q.front();q.pop(); if(vis[x])continue; vis[x]=1; v.push_back(x); for(auto y:v){ string z=calc(x,y); q.push(z); } } int curbase1=1,curbase2=1; for(int i=1;i<=n;i++){ pref[i][0]=add(pref[i-1][0],curbase1,MOD1); pref[i][1]=add(pref[i-1][1],curbase2,MOD2); curbase1=mul(curbase1,BASE1,MOD1); curbase2=mul(curbase2,BASE2,MOD2); } vector<int> res0,res1; for(string s:v){ int cur0,cur1;cur0=cur1=0; for(int i=0;i<(int)s.length();i++){ cur0=add(cur0,mul(mp[s[i]],add(pref[i+1][0],-pref[i][0],MOD1),MOD1),MOD1); cur1=add(cur1,mul(mp[s[i]],add(pref[i+1][1],-pref[i][1],MOD2),MOD2),MOD2); } res0.push_back(cur0); res1.push_back(cur1); } int t;cin>>t; cin>>s; build(1,1,n); int flag=0; for(int i=0;i<(int)res0.size();i++){ if(tree[1][0]==res0[i]&&tree[1][1]==res1[i]){ flag=1; } } flag?cout<<"Yes\n":cout<<"No\n"; for(;t;t--){ int l,r;cin>>l>>r; char c;cin>>c; int x=mp[c]; upd(1,1,n,l,r,x); int flag=0; for(int i=0;i<(int)res0.size();i++){ if(tree[1][0]==res0[i]&&tree[1][1]==res1[i]){ flag=1; } } flag?cout<<"Yes\n":cout<<"No\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...