Submission #507621

#TimeUsernameProblemLanguageResultExecution timeMemory
507621nichkeCrossing (JOI21_crossing)C++14
26 / 100
354 ms18360 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 BASE=3; const int MOD1=(int)1e9+9; const int MOD2=(int)1e9+6; 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); map<string,int> vis; for(int i=0;i<3;i++)cin>>v[i],vis[v[i]]=1; for(int i=0;i<(int)v.size();i++){ for(int j=0;j<(int)v.size();j++){ string nxt=calc(v[i],v[j]); if(vis[nxt])continue; v.push_back(nxt); vis[nxt]=1; } } 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,BASE,MOD1); curbase2=mul(curbase2,BASE,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...