#include <bits/stdc++.h>
#define int long long
using namespace std;
const int M = 1 << 18, N = 2 * M, MOD = 1e9 + 7;
deque<int> mini;
int n, q, ans = 0, val[3][M], hashval[N], len[M], pow3[M+1], cumP[M+1], tag_a[N], tag_b[N];
inline void updNode(int i, int a, int b, int d, int f) {
if(a == 0) {
tag_a[i] = 0;
tag_b[i] = b;
hashval[i] = (b * cumP[f - d]) % MOD;
}
}
int update(int i, int deb, int fin, int a, int b, int d = 0, int f = M) {
if(deb <= d && f <= fin) {
updNode(i, a, b, d, f);
return hashval[i];
}
if(f <= deb || fin <= d)
return 0;
int med = (d + f) >> 1;
updNode(i*2, tag_a[i], tag_b[i], d, med);
updNode(i*2+1, tag_a[i], tag_b[i], med, f);
tag_a[i] = 1;
tag_b[i] = 0;
int val1 = update(i*2, deb, fin, a, b, d, med),
val2 = update(i*2+1, deb, fin, a, b, med, f);
hashval[i] = (hashval[i*2] * pow3[f-med] + hashval[i*2+1]) % MOD;
if(deb < med && med < fin)
return (val1 * pow3[fin-med] + val2) % MOD;
else
return max(val1, val2);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 0; i < N; i++)
tag_a[i] = 1;
for(int i = 0; i < 3; i++) {
for(int j = 0; j < n; j++) {
char c; cin >> c;
if(c == 'O')
val[i][j] = 1;
else if(c == 'I')
val[i][j] = 2;
}
}
set<int> pos;
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
for(int k = 0; k < 3; k++) {
int hashing = 0;
for(int l = 0; l < n; l++)
hashing = (hashing * 3 + (i * val[0][l] + j * val[1][l] + k * val[2][l]) % 3) % MOD;
pos.insert(hashing);
}
pow3[0] = 1;
for(int i = 1; i <= M; i++)
pow3[i] = (pow3[i-1] * 3) % MOD;
for(int i = 1; i <= M; i++)
cumP[i] = (pow3[i-1] + cumP[i-1]) % MOD;
cin >> q;
for(int i = 0; i < n; i++) {
char c; cin >> c;
if(c == 'O')
update(1, i, i+1, 0, 1);
else if(c == 'I')
update(1, i, i+1, 0, 2);
}
if(pos.find(update(1, 0, n, 1, 0)) == pos.end())
cout << "No\n";
else
cout << "Yes\n";
for(int i = 0; i < q; i++) {
char c;
int deb, fin;
cin >> deb >> fin >> c;
deb--;
if(c == 'J')
update(1, deb, fin, 0, 0);
else if(c == 'O')
update(1, deb, fin, 0, 1);
else if(c == 'I')
update(1, deb, fin, 0, 2);
if(pos.find(update(1, 0, n, 1, 0)) == pos.end())
cout << "No\n";
else
cout << "Yes\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
139 ms |
9668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
139 ms |
9668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
139 ms |
9668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
139 ms |
9668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
