#include <bits/stdc++.h>
#define index int mid=(a+b)/2,le=2*node+1,ri=2*node+2;
using namespace std;
typedef long long ll;
const int MAX_N=2e5+10;
const int MAX_P=MAX_N*4;
struct dato{
int nj,no,ni;
};
bool tr[MAX_P];
char la[MAX_P];
dato ini[MAX_P],act[MAX_P];
string a,b,c,y;
dato join(dato a,dato b){
return {a.nj+b.nj,a.no+b.no,a.ni+b.ni};
}
void init(int node,int a,int b){
if(a==b){
if(c[a]==y[a]) tr[node]=1;
else tr[node]=0;
la[node]='#';
ini[node]=act[node]={0,0,0};
if(c[a]=='J') ini[node].nj++;
if(c[a]=='O') ini[node].no++;
if(c[a]=='I') ini[node].ni++;
if(y[a]=='J') act[node].nj++;
if(y[a]=='O') act[node].no++;
if(y[a]=='I') act[node].ni++;
return;
}
index;
init(le,a,mid);
init(ri,mid+1,b);
tr[node]=tr[le]&tr[ri];
la[node]='#';
ini[node]=join(ini[le],ini[ri]);
act[node]=join(act[le],act[ri]);
}
bool igual(int a){
if(ini[a].nj==act[a].nj && ini[a].no==act[a].no && ini[a].ni==act[a].ni) return 1;
return 0;
}
void propagar(int node,int a,int b){
if(la[node]=='#') return;
char aux=la[node];
act[node]={0,0,0};
if(aux=='J') act[node].nj=(a-b)+1;
if(aux=='O') act[node].no=(a-b)+1;
if(aux=='I') act[node].ni=(a-b)+1;
if(igual(node)){
tr[node]=1;
}
la[node]='#';
if(a==b) return;
index;
la[le]=aux;
la[ri]=aux;
}
void update(int node,int a,int b,int l,int r,char val){
propagar(node,a,b);
if(l>b || r<a) return;
if(l<=a && r>=b){
la[node]=val;
propagar(node,a,b);
return;
}
index;
update(le,a,mid,l,r,val);
update(ri,mid+1,b,l,r,val);
act[node]=join(act[le],act[ri]);
tr[node]=tr[le]&tr[ri];
}
int main(){
int n,q;
cin>>n;
cin>>a>>b>>c;
cin>>q>>y;
if(y==a) cout<<"Yes\n";
else cout<<"No\n";
init(0,0,n-1);
for(int i=0;i<q;i++){
int l,r;
char x;
cin>>l>>r>>x;
l--; r--;
update(0,0,n-1,l,r,x);
if(tr[0]) cout<<"Yes\n";
else cout<<"No\n";
}
}
Compilation message
Main.cpp: In function 'void propagar(int, int, int)':
Main.cpp:2:19: warning: unused variable 'mid' [-Wunused-variable]
2 | #define index int mid=(a+b)/2,le=2*node+1,ri=2*node+2;
| ^~~
Main.cpp:55:3: note: in expansion of macro 'index'
55 | index;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
448 ms |
2328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
448 ms |
2328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
448 ms |
2328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
448 ms |
2328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
