#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 2e5 + 10;
const int alpha = 27;
int base[2] = {313, 369}, mod[2] = {(int)1e9+7, (int)1e9+9};
int n, q, a[maxn][3], pw[maxn][2], val[maxn][3][2], seg[maxn << 2][2], lazy[maxn << 2];
int hsh[alpha][2];
bool mark[alpha];
void shift(int v, int l, int r);
void change(int v, int l, int r, int ql, int qr, int x){
if (qr <= l || r <= ql) return;
if (ql <= l && r <= qr){
seg[v][0] = val[r-l][x][0];
seg[v][1] = val[r-l][x][1];
lazy[v] = x;
return;
}
shift(v, l, r);
int mid = (l + r) >> 1;
change(v << 1, l, mid, ql, qr, x);
change(v << 1 | 1, mid, r, ql, qr, x);
for (int i = 0; i < 2; i++){
seg[v][i] = (1ll * seg[v << 1][i] * pw[r-mid][i] + seg[v << 1 | 1][i]) % mod[i];
}
}
void shift(int v, int l, int r){
if (lazy[v] == -1) return;
int mid = (l + r) >> 1;
change(v << 1, l, mid, l, mid, lazy[v]);
change(v << 1 | 1, mid, r, mid, r, lazy[v]);
lazy[v] = -1;
}
bool check(){
for (int i = 0; i < alpha; i++){
if (mark[i] && MP(hsh[i][0], hsh[i][1]) == MP(seg[1][0], seg[1][1])) return true;
}
return false;
}
int main(){
memset(lazy, -1, sizeof lazy);
string s[3];
cin >> n >> s[0] >> s[1] >> s[2];
for (int j = 0; j < 3; j++){
for (int i = 1; i <= n; i++){
a[i][j] = (s[j][i-1] == 'J'? 0: (s[j][i-1] == 'O'? 1: 2));
// debug(i, j, a[i][j]);
}
}
pw[0][0] = pw[0][1] = 1;
for (int i = 1; i <= n; i++){
for (int j = 0; j < 2; j++){
pw[i][j] = 1ll * pw[i-1][j] * base[j] % mod[j];
}
}
for (int i = 1; i <= n; i++){
for (int j = 0; j < 3; j++){
for (int k = 0; k < 2; k++){
val[i][j][k] = (1ll * val[i-1][j][k] * base[k] + (j+1)) % mod[k];
}
}
}
for (int x1 = 0; x1 < 3; x1++){
for (int x2 = 0; x2 < 3; x2++){
for (int x3 = 0; x3 < 3; x3++){
if ((x1 + x2 + x3) % 3 == 0) continue;
int idx = x3 + x2 * 3 + x1 * 9;
//debug(x1, x2, x3, idx);
mark[idx] = true;
for (int i = 1; i <= n; i++){
int tmp = (a[i][0] * x1 + a[i][1] * x2 + a[i][2] * x3) % 3;
// if (x1 == 0 && x2 == 2 && x3 == 2) debug(i, tmp);
for (int j = 0; j < 2; j++){
hsh[idx][j] = (1ll * hsh[idx][j] * base[j] + (tmp+1)) % mod[j];
}
}
}
}
}
cin >> q;
string t;
cin >> t;
for (int i = 1; i <= n; i++){
int tmp = (t[i-1] == 'J'? 0: (t[i-1] == 'O'? 1: 2));
change(1, 1, n+1, i, i+1, tmp);
}
cout << (check()? "Yes\n": "No\n");
while(q--){
int l, r; char c; cin >> l >> r >> c;
int tmp = (c == 'J'? 0: (c == 'O'? 1: 2));
change(1, 1, n+1, l, r+1, tmp);
cout << (check()? "Yes\n": "No\n");
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
290 ms |
5364 KB |
Output is correct |
| 2 |
Correct |
323 ms |
5584 KB |
Output is correct |
| 3 |
Correct |
351 ms |
5368 KB |
Output is correct |
| 4 |
Incorrect |
300 ms |
5448 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
290 ms |
5364 KB |
Output is correct |
| 2 |
Correct |
323 ms |
5584 KB |
Output is correct |
| 3 |
Correct |
351 ms |
5368 KB |
Output is correct |
| 4 |
Incorrect |
300 ms |
5448 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
290 ms |
5364 KB |
Output is correct |
| 2 |
Correct |
323 ms |
5584 KB |
Output is correct |
| 3 |
Correct |
351 ms |
5368 KB |
Output is correct |
| 4 |
Incorrect |
300 ms |
5448 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
290 ms |
5364 KB |
Output is correct |
| 2 |
Correct |
323 ms |
5584 KB |
Output is correct |
| 3 |
Correct |
351 ms |
5368 KB |
Output is correct |
| 4 |
Incorrect |
300 ms |
5448 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
