// 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+7;
const int MOD2=(int)1e9+9;
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,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 time |
Memory |
Grader output |
1 |
Correct |
85 ms |
2248 KB |
Output is correct |
2 |
Correct |
86 ms |
2436 KB |
Output is correct |
3 |
Correct |
89 ms |
2244 KB |
Output is correct |
4 |
Correct |
70 ms |
2316 KB |
Output is correct |
5 |
Correct |
69 ms |
2320 KB |
Output is correct |
6 |
Correct |
69 ms |
2244 KB |
Output is correct |
7 |
Correct |
73 ms |
2500 KB |
Output is correct |
8 |
Correct |
75 ms |
2384 KB |
Output is correct |
9 |
Correct |
74 ms |
2360 KB |
Output is correct |
10 |
Incorrect |
71 ms |
2392 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
85 ms |
2248 KB |
Output is correct |
2 |
Correct |
86 ms |
2436 KB |
Output is correct |
3 |
Correct |
89 ms |
2244 KB |
Output is correct |
4 |
Correct |
70 ms |
2316 KB |
Output is correct |
5 |
Correct |
69 ms |
2320 KB |
Output is correct |
6 |
Correct |
69 ms |
2244 KB |
Output is correct |
7 |
Correct |
73 ms |
2500 KB |
Output is correct |
8 |
Correct |
75 ms |
2384 KB |
Output is correct |
9 |
Correct |
74 ms |
2360 KB |
Output is correct |
10 |
Incorrect |
71 ms |
2392 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
85 ms |
2248 KB |
Output is correct |
2 |
Correct |
86 ms |
2436 KB |
Output is correct |
3 |
Correct |
89 ms |
2244 KB |
Output is correct |
4 |
Correct |
70 ms |
2316 KB |
Output is correct |
5 |
Correct |
69 ms |
2320 KB |
Output is correct |
6 |
Correct |
69 ms |
2244 KB |
Output is correct |
7 |
Correct |
73 ms |
2500 KB |
Output is correct |
8 |
Correct |
75 ms |
2384 KB |
Output is correct |
9 |
Correct |
74 ms |
2360 KB |
Output is correct |
10 |
Incorrect |
71 ms |
2392 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
85 ms |
2248 KB |
Output is correct |
2 |
Correct |
86 ms |
2436 KB |
Output is correct |
3 |
Correct |
89 ms |
2244 KB |
Output is correct |
4 |
Correct |
70 ms |
2316 KB |
Output is correct |
5 |
Correct |
69 ms |
2320 KB |
Output is correct |
6 |
Correct |
69 ms |
2244 KB |
Output is correct |
7 |
Correct |
73 ms |
2500 KB |
Output is correct |
8 |
Correct |
75 ms |
2384 KB |
Output is correct |
9 |
Correct |
74 ms |
2360 KB |
Output is correct |
10 |
Incorrect |
71 ms |
2392 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |