# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
507632 | nichke | Crossing (JOI21_crossing) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// 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=102079;
const int BASE2=5002519;
const int MOD1=(int)1e9+9;
const int MOD2=(int)100002181;
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);
}
int qry(int v,int l,int r,int ql,int qr,int t){
if(l>r||ql>qr||l>qr||r<ql)return 0;
int m=(l+r)/2;
if()
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n;cin>>n;
mp['J']=0;
mp['O']=1;
mp['I']=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,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;
memset(lazy,-1,sizeof lazy);
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;
}