#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
int chg(char a){
if(a=='J'){
return 0;
}
if(a=='O'){
return 1;
}
if(a=='I'){
return 2;
}
}
vector<int> get(vector<int> a,vector<int> b){
int n=a.size();
vector<int> c(n);
for(int i=0;i<n;i++){
c[i]=(2*a[i]+2*b[i])%3;
}
return c;
}
vector<int> g;
struct ST{
struct no{
int x=0,xx=0,sum=0;
int sz=0;
int tag=-1;
};
int z=0;
vector<no> st;
void init(int x){
st.resize(4*x);
}
void build(int v,int L,int R){
if(L==R){
st[v].sum=g[L];
st[v].sz=1;
z+=g[L]*g[L];
return;
}
int m=(L+R)/2;
build(2*v+1,L,m);
build(2*v+2,m+1,R);
st[v].sz=st[2*v+1].sz+st[2*v+2].sz;
st[v].sum=st[2*v+1].sum+st[2*v+2].sum;
}
void pull(int v){
st[v].x=st[2*v+1].x+st[2*v+2].x;
st[v].xx=st[2*v+1].xx+st[2*v+2].xx;
}
void upd(int v,int x){
st[v].tag=x;
st[v].xx=st[v].sz*x*x;
st[v].x=st[v].sum*x;
}
void pudo(int v){
if(st[v].tag==-1){
return;
}
upd(2*v+1,st[v].tag);
upd(2*v+2,st[v].tag);
st[v].tag=-1;
}
void update(int v,int L,int R,int l,int r,int k){
if(l==L && r==R){
upd(v,k);
return;
}
int m=(L+R)/2;
pudo(v);
if(r<=m){
update(2*v+1,L,m,l,r,k);
}
else if(l>m){
update(2*v+2,m+1,R,l,r,k);
}
else{
update(2*v+1,L,m,l,m,k);
update(2*v+2,m+1,R,m+1,r,k);
}
pull(v);
}
bool query(){
return (st[0].xx-2*st[0].x+z)==0;
}
};
int main(){
AquA;
int n;
cin >> n;
string a,b,c;
cin >> a >> b >> c;
vector<vector<int> > v(3,vector<int>(n));
for(int i=0;i<n;i++){
v[0][i]=chg(a[i]);
v[1][i]=chg(b[i]);
v[2][i]=chg(c[i]);
}
v.push_back(get(v[0],v[1]));
v.push_back(get(v[1],v[2]));
v.push_back(get(v[0],v[2]));
v.push_back(get(v[3],v[2]));
v.push_back(get(v[4],v[0]));
v.push_back(get(v[5],v[1]));
int q;
cin >> q;
string t;
cin >> t;
vector<int> p(n);
for(int i=0;i<n;i++){
p[i]=chg(t[i]);
}
vector<pair<pair<int,int>,int> > vq(q);
for(int i=0;i<q;i++){
cin >> vq[i].fs.fs >> vq[i].fs.sc;
char c;
cin >> c;
vq[i].sc=chg(c);
}
vector<int> ans(q+1);
for(int i=0;i<9;i++){
g=v[i];
ST st;
st.init(n);
st.build(0,0,n-1);
for(int j=0;j<n;j++){
st.update(0,0,n-1,j,j,p[j]);
}
ans[0]|=st.query();
for(int j=0;j<q;j++){
st.update(0,0,n-1,vq[j].fs.fs-1,vq[j].fs.sc-1,vq[j].sc);
ans[j+1]|=st.query();
}
}
for(int i=0;i<=q;i++){
if(ans[i]){
cout << "Yes\n";
}
else{
cout << "No\n";
}
}
return 0;
}
Compilation message
Main.cpp: In function 'int chg(char)':
Main.cpp:19:1: warning: control reaches end of non-void function [-Wreturn-type]
19 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
231 ms |
5164 KB |
Output is correct |
2 |
Correct |
286 ms |
5524 KB |
Output is correct |
3 |
Correct |
249 ms |
5380 KB |
Output is correct |
4 |
Correct |
204 ms |
5428 KB |
Output is correct |
5 |
Correct |
200 ms |
5396 KB |
Output is correct |
6 |
Correct |
200 ms |
5228 KB |
Output is correct |
7 |
Correct |
201 ms |
5432 KB |
Output is correct |
8 |
Correct |
216 ms |
5640 KB |
Output is correct |
9 |
Correct |
223 ms |
5580 KB |
Output is correct |
10 |
Correct |
216 ms |
5568 KB |
Output is correct |
11 |
Correct |
217 ms |
5508 KB |
Output is correct |
12 |
Correct |
218 ms |
5500 KB |
Output is correct |
13 |
Correct |
226 ms |
5580 KB |
Output is correct |
14 |
Correct |
223 ms |
5508 KB |
Output is correct |
15 |
Correct |
220 ms |
5580 KB |
Output is correct |
16 |
Correct |
214 ms |
5480 KB |
Output is correct |
17 |
Correct |
249 ms |
5508 KB |
Output is correct |
18 |
Correct |
219 ms |
5432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
231 ms |
5164 KB |
Output is correct |
2 |
Correct |
286 ms |
5524 KB |
Output is correct |
3 |
Correct |
249 ms |
5380 KB |
Output is correct |
4 |
Correct |
204 ms |
5428 KB |
Output is correct |
5 |
Correct |
200 ms |
5396 KB |
Output is correct |
6 |
Correct |
200 ms |
5228 KB |
Output is correct |
7 |
Correct |
201 ms |
5432 KB |
Output is correct |
8 |
Correct |
216 ms |
5640 KB |
Output is correct |
9 |
Correct |
223 ms |
5580 KB |
Output is correct |
10 |
Correct |
216 ms |
5568 KB |
Output is correct |
11 |
Correct |
217 ms |
5508 KB |
Output is correct |
12 |
Correct |
218 ms |
5500 KB |
Output is correct |
13 |
Correct |
226 ms |
5580 KB |
Output is correct |
14 |
Correct |
223 ms |
5508 KB |
Output is correct |
15 |
Correct |
220 ms |
5580 KB |
Output is correct |
16 |
Correct |
214 ms |
5480 KB |
Output is correct |
17 |
Correct |
249 ms |
5508 KB |
Output is correct |
18 |
Correct |
219 ms |
5432 KB |
Output is correct |
19 |
Correct |
1340 ms |
33408 KB |
Output is correct |
20 |
Correct |
1175 ms |
33216 KB |
Output is correct |
21 |
Correct |
856 ms |
31428 KB |
Output is correct |
22 |
Correct |
887 ms |
28776 KB |
Output is correct |
23 |
Correct |
419 ms |
7784 KB |
Output is correct |
24 |
Correct |
418 ms |
7628 KB |
Output is correct |
25 |
Correct |
978 ms |
33396 KB |
Output is correct |
26 |
Correct |
961 ms |
33324 KB |
Output is correct |
27 |
Correct |
984 ms |
33316 KB |
Output is correct |
28 |
Correct |
1047 ms |
33296 KB |
Output is correct |
29 |
Correct |
977 ms |
32444 KB |
Output is correct |
30 |
Correct |
477 ms |
7784 KB |
Output is correct |
31 |
Correct |
1100 ms |
33324 KB |
Output is correct |
32 |
Correct |
1093 ms |
30792 KB |
Output is correct |
33 |
Correct |
452 ms |
7576 KB |
Output is correct |
34 |
Correct |
1110 ms |
33388 KB |
Output is correct |
35 |
Correct |
813 ms |
26204 KB |
Output is correct |
36 |
Correct |
441 ms |
7604 KB |
Output is correct |
37 |
Correct |
458 ms |
7756 KB |
Output is correct |
38 |
Correct |
1053 ms |
33080 KB |
Output is correct |
39 |
Correct |
724 ms |
33456 KB |
Output is correct |
40 |
Correct |
751 ms |
24148 KB |
Output is correct |
41 |
Correct |
1483 ms |
33568 KB |
Output is correct |
42 |
Correct |
365 ms |
32796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
231 ms |
5164 KB |
Output is correct |
2 |
Correct |
286 ms |
5524 KB |
Output is correct |
3 |
Correct |
249 ms |
5380 KB |
Output is correct |
4 |
Correct |
204 ms |
5428 KB |
Output is correct |
5 |
Correct |
200 ms |
5396 KB |
Output is correct |
6 |
Correct |
200 ms |
5228 KB |
Output is correct |
7 |
Correct |
201 ms |
5432 KB |
Output is correct |
8 |
Correct |
216 ms |
5640 KB |
Output is correct |
9 |
Correct |
223 ms |
5580 KB |
Output is correct |
10 |
Correct |
216 ms |
5568 KB |
Output is correct |
11 |
Correct |
217 ms |
5508 KB |
Output is correct |
12 |
Correct |
218 ms |
5500 KB |
Output is correct |
13 |
Correct |
226 ms |
5580 KB |
Output is correct |
14 |
Correct |
223 ms |
5508 KB |
Output is correct |
15 |
Correct |
220 ms |
5580 KB |
Output is correct |
16 |
Correct |
214 ms |
5480 KB |
Output is correct |
17 |
Correct |
249 ms |
5508 KB |
Output is correct |
18 |
Correct |
219 ms |
5432 KB |
Output is correct |
19 |
Correct |
264 ms |
5304 KB |
Output is correct |
20 |
Correct |
255 ms |
5384 KB |
Output is correct |
21 |
Correct |
219 ms |
5484 KB |
Output is correct |
22 |
Correct |
192 ms |
5088 KB |
Output is correct |
23 |
Correct |
214 ms |
5580 KB |
Output is correct |
24 |
Correct |
222 ms |
5408 KB |
Output is correct |
25 |
Correct |
237 ms |
5496 KB |
Output is correct |
26 |
Correct |
206 ms |
5320 KB |
Output is correct |
27 |
Correct |
221 ms |
5476 KB |
Output is correct |
28 |
Correct |
206 ms |
5092 KB |
Output is correct |
29 |
Correct |
232 ms |
5476 KB |
Output is correct |
30 |
Correct |
195 ms |
5188 KB |
Output is correct |
31 |
Correct |
220 ms |
5628 KB |
Output is correct |
32 |
Correct |
206 ms |
5464 KB |
Output is correct |
33 |
Correct |
220 ms |
5476 KB |
Output is correct |
34 |
Correct |
186 ms |
5204 KB |
Output is correct |
35 |
Correct |
210 ms |
5580 KB |
Output is correct |
36 |
Correct |
219 ms |
5504 KB |
Output is correct |
37 |
Correct |
213 ms |
5480 KB |
Output is correct |
38 |
Correct |
220 ms |
5488 KB |
Output is correct |
39 |
Correct |
216 ms |
5580 KB |
Output is correct |
40 |
Correct |
218 ms |
5508 KB |
Output is correct |
41 |
Correct |
213 ms |
5524 KB |
Output is correct |
42 |
Correct |
217 ms |
5508 KB |
Output is correct |
43 |
Correct |
200 ms |
5436 KB |
Output is correct |
44 |
Correct |
218 ms |
5504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
231 ms |
5164 KB |
Output is correct |
2 |
Correct |
286 ms |
5524 KB |
Output is correct |
3 |
Correct |
249 ms |
5380 KB |
Output is correct |
4 |
Correct |
204 ms |
5428 KB |
Output is correct |
5 |
Correct |
200 ms |
5396 KB |
Output is correct |
6 |
Correct |
200 ms |
5228 KB |
Output is correct |
7 |
Correct |
201 ms |
5432 KB |
Output is correct |
8 |
Correct |
216 ms |
5640 KB |
Output is correct |
9 |
Correct |
223 ms |
5580 KB |
Output is correct |
10 |
Correct |
216 ms |
5568 KB |
Output is correct |
11 |
Correct |
217 ms |
5508 KB |
Output is correct |
12 |
Correct |
218 ms |
5500 KB |
Output is correct |
13 |
Correct |
226 ms |
5580 KB |
Output is correct |
14 |
Correct |
223 ms |
5508 KB |
Output is correct |
15 |
Correct |
220 ms |
5580 KB |
Output is correct |
16 |
Correct |
214 ms |
5480 KB |
Output is correct |
17 |
Correct |
249 ms |
5508 KB |
Output is correct |
18 |
Correct |
219 ms |
5432 KB |
Output is correct |
19 |
Correct |
1340 ms |
33408 KB |
Output is correct |
20 |
Correct |
1175 ms |
33216 KB |
Output is correct |
21 |
Correct |
856 ms |
31428 KB |
Output is correct |
22 |
Correct |
887 ms |
28776 KB |
Output is correct |
23 |
Correct |
419 ms |
7784 KB |
Output is correct |
24 |
Correct |
418 ms |
7628 KB |
Output is correct |
25 |
Correct |
978 ms |
33396 KB |
Output is correct |
26 |
Correct |
961 ms |
33324 KB |
Output is correct |
27 |
Correct |
984 ms |
33316 KB |
Output is correct |
28 |
Correct |
1047 ms |
33296 KB |
Output is correct |
29 |
Correct |
977 ms |
32444 KB |
Output is correct |
30 |
Correct |
477 ms |
7784 KB |
Output is correct |
31 |
Correct |
1100 ms |
33324 KB |
Output is correct |
32 |
Correct |
1093 ms |
30792 KB |
Output is correct |
33 |
Correct |
452 ms |
7576 KB |
Output is correct |
34 |
Correct |
1110 ms |
33388 KB |
Output is correct |
35 |
Correct |
813 ms |
26204 KB |
Output is correct |
36 |
Correct |
441 ms |
7604 KB |
Output is correct |
37 |
Correct |
458 ms |
7756 KB |
Output is correct |
38 |
Correct |
1053 ms |
33080 KB |
Output is correct |
39 |
Correct |
724 ms |
33456 KB |
Output is correct |
40 |
Correct |
751 ms |
24148 KB |
Output is correct |
41 |
Correct |
1483 ms |
33568 KB |
Output is correct |
42 |
Correct |
365 ms |
32796 KB |
Output is correct |
43 |
Correct |
264 ms |
5304 KB |
Output is correct |
44 |
Correct |
255 ms |
5384 KB |
Output is correct |
45 |
Correct |
219 ms |
5484 KB |
Output is correct |
46 |
Correct |
192 ms |
5088 KB |
Output is correct |
47 |
Correct |
214 ms |
5580 KB |
Output is correct |
48 |
Correct |
222 ms |
5408 KB |
Output is correct |
49 |
Correct |
237 ms |
5496 KB |
Output is correct |
50 |
Correct |
206 ms |
5320 KB |
Output is correct |
51 |
Correct |
221 ms |
5476 KB |
Output is correct |
52 |
Correct |
206 ms |
5092 KB |
Output is correct |
53 |
Correct |
232 ms |
5476 KB |
Output is correct |
54 |
Correct |
195 ms |
5188 KB |
Output is correct |
55 |
Correct |
220 ms |
5628 KB |
Output is correct |
56 |
Correct |
206 ms |
5464 KB |
Output is correct |
57 |
Correct |
220 ms |
5476 KB |
Output is correct |
58 |
Correct |
186 ms |
5204 KB |
Output is correct |
59 |
Correct |
210 ms |
5580 KB |
Output is correct |
60 |
Correct |
219 ms |
5504 KB |
Output is correct |
61 |
Correct |
213 ms |
5480 KB |
Output is correct |
62 |
Correct |
220 ms |
5488 KB |
Output is correct |
63 |
Correct |
216 ms |
5580 KB |
Output is correct |
64 |
Correct |
218 ms |
5508 KB |
Output is correct |
65 |
Correct |
213 ms |
5524 KB |
Output is correct |
66 |
Correct |
217 ms |
5508 KB |
Output is correct |
67 |
Correct |
200 ms |
5436 KB |
Output is correct |
68 |
Correct |
218 ms |
5504 KB |
Output is correct |
69 |
Correct |
1147 ms |
28416 KB |
Output is correct |
70 |
Correct |
1186 ms |
33208 KB |
Output is correct |
71 |
Correct |
421 ms |
7728 KB |
Output is correct |
72 |
Correct |
425 ms |
7708 KB |
Output is correct |
73 |
Correct |
406 ms |
7680 KB |
Output is correct |
74 |
Correct |
858 ms |
28460 KB |
Output is correct |
75 |
Correct |
408 ms |
7616 KB |
Output is correct |
76 |
Correct |
945 ms |
33336 KB |
Output is correct |
77 |
Correct |
886 ms |
28608 KB |
Output is correct |
78 |
Correct |
410 ms |
7624 KB |
Output is correct |
79 |
Correct |
409 ms |
7644 KB |
Output is correct |
80 |
Correct |
794 ms |
25148 KB |
Output is correct |
81 |
Correct |
418 ms |
7740 KB |
Output is correct |
82 |
Correct |
942 ms |
33308 KB |
Output is correct |
83 |
Correct |
914 ms |
31568 KB |
Output is correct |
84 |
Correct |
403 ms |
7608 KB |
Output is correct |
85 |
Correct |
412 ms |
7592 KB |
Output is correct |
86 |
Correct |
938 ms |
26600 KB |
Output is correct |
87 |
Correct |
1054 ms |
33292 KB |
Output is correct |
88 |
Correct |
461 ms |
7704 KB |
Output is correct |
89 |
Correct |
933 ms |
29844 KB |
Output is correct |
90 |
Correct |
1035 ms |
33340 KB |
Output is correct |
91 |
Correct |
452 ms |
7612 KB |
Output is correct |
92 |
Correct |
804 ms |
26192 KB |
Output is correct |
93 |
Correct |
407 ms |
7588 KB |
Output is correct |
94 |
Correct |
407 ms |
7640 KB |
Output is correct |
95 |
Correct |
414 ms |
7660 KB |
Output is correct |
96 |
Correct |
1026 ms |
33080 KB |
Output is correct |
97 |
Correct |
702 ms |
33456 KB |
Output is correct |
98 |
Correct |
746 ms |
24148 KB |
Output is correct |
99 |
Correct |
1366 ms |
33564 KB |
Output is correct |
100 |
Correct |
355 ms |
32900 KB |
Output is correct |