#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < n; i++)
#define debug(x) cout<<#x<<" is " <<x<<endl;
typedef long long ll;
const ll N=200010, MOD=1e9+9;
string A[4],T;
char ch;
ll n, Q,val[10],l,r,q,cur, mul[N], mmm[N];
ll jj(char x){
if(x=='J')return 0;
if(x=='O')return 1;
return 2;
}
int jjj(char x, char y){
if(x==y) return jj(x);
else return (3-jj(x)-jj(y));
}
int jjjj(int x, int y){
if(x==y) return x;
else return (3-x-y);
}
ll convert(string x){
ll ans=0;
rep(i,n){
//cout<<jj(x[i])*mul[i]<<' ';
ans+=jj(x[i])*mul[i];
ans%=MOD;
}
//cout<<endl;
return ans;
}
ll conver(string x, string y){
ll ans=0;
rep(i,n){
ans+=jjj(x[i],y[i])*mul[i];
ans%=MOD;
}
return ans;
}
ll conve(string x, string y,string z){
ll ans=0;
rep(i,n){
ans+=jjjj(jj(z[i]),jjj(x[i],y[i]))*mul[i];
ans%=MOD;
}
return ans;
}
struct node{
ll s,e,m,lazy,val;
node *l, *r;
node (int S, int E){
s=S,e=E,m=(s+e)/2,val=0,lazy=-1;
if(s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void propogate(){
if(lazy==-1) return;
val=lazy*(mmm[e]-(s==0 ? 0: mmm[s-1]));//cout<<lazy<<' '<<mmm[e]-(s==0 ? 0: mmm[s-1])<<endl;
if(s!=e){
l->lazy=lazy;
r->lazy=lazy;
}
lazy=-1;
}
void set(int S, int E, ll V){
if(s==S&&e==E)lazy=V;
else{
if(E<=m)l->set(S,E,V);
else if(m<S) r-> set(S,E,V);
else l->set(S,m,V), r->set(m+1,E,V);
l->propogate(), r->propogate();
val=l->val+r->val;
}
}
ll query(int S, int E){
propogate();
if(s==S&&e==E)return val;
else if(E<=m) return l->query(S,E);
else if(m<S) return r->query(S,E);
else return l->query(S,m)+r->query(m+1,E);
}
} *root;
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);
cin>>n>>A[0]>>A[1]>>A[2]>>Q>>T;
mul[0]=1;
rep(i,n)mul[i+1]=(mul[i]*3)%MOD;
mmm[0]=1;
rep(i,n)mmm[i+1]=(mul[i+1]+mmm[i])%MOD;
rep(i,3) val[i]=convert(A[i]);
rep(i,3) val[i+3]=conver(A[i],A[(i+1)%3]);
rep(i,3) val[i+6]=conve(A[i],A[(i+1)%3],A[(i+2)%3]);
//rep(i,9)cout<<val[i]<<' ';cout<<endl;
root= new node(0,200010);
rep(i,n){
//cout<<"set: "<<i<<endl;
root->set(i,i,jj(T[i]));
}
ll cur=root->query(0,n);
bool flag=true;
rep(i,9){
if(cur==val[i]){
flag=false,cout<<"Yes\n";
break;
}
}
//rep(i,n)cout<<root->query(i,i)<<' ';
if(flag)cout<<"No\n";
while(Q--){
cin>>l>>r>>ch;
l--,r--;
root->set(l,r,jj(ch));
ll cur=root->query(0,n-1);
//rep(i,n)cout<<root->query(i,i)<<' ';
//cout<<cur<<' ';
bool flag=true;
rep(i,9)if(cur==val[i]){
flag=false,cout<<"Yes\n";
break;
}
if(flag)cout<<"No\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
25900 KB |
Output is correct |
| 2 |
Correct |
95 ms |
25888 KB |
Output is correct |
| 3 |
Correct |
106 ms |
25928 KB |
Output is correct |
| 4 |
Incorrect |
101 ms |
25932 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
25900 KB |
Output is correct |
| 2 |
Correct |
95 ms |
25888 KB |
Output is correct |
| 3 |
Correct |
106 ms |
25928 KB |
Output is correct |
| 4 |
Incorrect |
101 ms |
25932 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
25900 KB |
Output is correct |
| 2 |
Correct |
95 ms |
25888 KB |
Output is correct |
| 3 |
Correct |
106 ms |
25928 KB |
Output is correct |
| 4 |
Incorrect |
101 ms |
25932 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
25900 KB |
Output is correct |
| 2 |
Correct |
95 ms |
25888 KB |
Output is correct |
| 3 |
Correct |
106 ms |
25928 KB |
Output is correct |
| 4 |
Incorrect |
101 ms |
25932 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
