#include<bits/stdc++.h>
using namespace std;
int troll(char a) {
if(a == 'J') {
return 0;
}
else if(a == 'O') {
return 1;
}
else {
return 2;
}
}
vector<int> seg(1000001);
vector<pair<int,int>> wow(1000001,{-2,-1});
vector<int> banana(1000001,-1);
int idk[1000001][3];
int no[9][3] = {{0,0,1},{0,1,0},{1,0,0},{2,2,0},{2,0,2},{0,2,2},{1,1,2},{1,2,1},{2,1,1}};
int pr[200001][3];
vector<int> a(200001);
vector<int> b(200001);
vector<int> c(200001);
vector<int> s(200001);
void upd(int l, int r, int ql, int qr, int x, int col, pair<int,int> z, int t) {
if(l == ql && r == qr) {
seg[x] = idk[x][col];
wow[x] = {t,col};
banana[x] = t;
return;
}
int mid = (l+r)/2;
z = max(z,wow[x]);
if(qr <= mid) {
upd(l,mid,ql,qr,x*2,col,z,t);
}
else if(ql > mid) {
upd(mid+1,r,ql,qr,x*2+1,col,z,t);
}
else {
upd(l,mid,ql,mid,x*2,col,z,t);
upd(mid+1,r,mid+1,r,x*2+1,col,z,t);
}
int a,b;
if(z.first > banana[x*2]) {
a = idk[x*2][z.second];
}
else {
a = seg[x*2];
}
if(z.first > banana[x*2+1]) {
b = idk[x*2+1][z.second];
}
else {
b = seg[x*2+1];
}
seg[x] = (a&b);
banana[x] = t;
}
void build(int l, int r, int x) {
if(l == r) {
seg[x] = pr[l][s[l]];
idk[x][0] = pr[l][0];
idk[x][1] = pr[l][1];
idk[x][2] = pr[l][2];
return;
}
int mid = (l+r)/2;
build(l,mid,x*2);
build(mid+1,r,x*2+1);
idk[x][0] = (idk[x*2][0]&idk[x*2+1][0]);
idk[x][1] = (idk[x*2][1]&idk[x*2+1][1]);
idk[x][2] = (idk[x*2][2]&idk[x*2+1][2]);
seg[x] = (seg[x*2]&seg[x*2+1]);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,q;
cin >> n;
char x;
for(int i = 0; i <= n; i++) {
for(int j = 0; j < 9; j++) {
pr[i][j] = 0;
}
}
for(int i = 1; i <= n; i++) {
cin >> x;
a[i] = troll(x);
}
for(int i = 1; i <= n; i++) {
cin >> x;
b[i] = troll(x);
}
for(int i = 1; i <= n; i++) {
cin >> x;
c[i] = troll(x);
}
cin >> q;
for(int i = 1; i <= n; i++) {
cin >> x;
s[i] = troll(x);
}
for(int i = 1; i <= n; i++) {
for(int j = 0; j < 9; j++) {
int br = (a[i]*no[j][0]+b[i]*no[j][1]+c[i]*no[j][2])%3;
pr[i][br]+=(1 << j);
}
}
build(1,n,1);
if(seg[1] > 0) {
cout << "Yes\n";
}
else {
cout << "No\n";
}
for(int i = 0; i < q; i++) {
int l,r;
cin >> l >> r >> x;
int br = troll(x);
upd(1,n,l,r,1,br,{-1,-1},i);
if(seg[1] > 0) {
cout << "Yes\n";
}
else {
cout << "No\n";
}
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:92:22: warning: iteration 3 invokes undefined behavior [-Waggressive-loop-optimizations]
92 | pr[i][j] = 0;
| ~~~~~~~~~^~~
Main.cpp:91:26: note: within this loop
91 | for(int j = 0; j < 9; j++) {
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
23208 KB |
Output is correct |
| 2 |
Correct |
33 ms |
23432 KB |
Output is correct |
| 3 |
Correct |
32 ms |
23132 KB |
Output is correct |
| 4 |
Incorrect |
33 ms |
23120 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
23208 KB |
Output is correct |
| 2 |
Correct |
33 ms |
23432 KB |
Output is correct |
| 3 |
Correct |
32 ms |
23132 KB |
Output is correct |
| 4 |
Incorrect |
33 ms |
23120 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
23208 KB |
Output is correct |
| 2 |
Correct |
33 ms |
23432 KB |
Output is correct |
| 3 |
Correct |
32 ms |
23132 KB |
Output is correct |
| 4 |
Incorrect |
33 ms |
23120 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
23208 KB |
Output is correct |
| 2 |
Correct |
33 ms |
23432 KB |
Output is correct |
| 3 |
Correct |
32 ms |
23132 KB |
Output is correct |
| 4 |
Incorrect |
33 ms |
23120 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
