// Be name khoda //
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) x.begin(), x.end()
#define pb push_back
#define fi first
#define se second
#define mp make_pair
const int maxn5 = 2e5 + 10;
const int maxnt = 1e6 + 10;
ll mod[2] = {1000000007, 1000000009};
ll base[2] = {21163, 21269};
int n, t[maxn5];
pair <ll, ll> hsh[maxnt];
int lazy[maxnt];
string s[3];
ll pw[2][maxn5], ps[2][maxn5];
set <pair<ll, ll>> av;
bool mark[100];
int get_val(char c){
if(c == 'J')
return 0;
if(c == 'O')
return 1;
return 2;
}
struct zarib{
int x[3];
int num;
zarib(){
x[0] = x[1] = x[2] = num = 0;
}
} q[100];
zarib comb(zarib a, zarib b){
zarib ret;
//cout << a.x[0] << ' ' << b.x[0] << endl;
ret.x[0] = (6 - a.x[0] - b.x[0]) % 3;
ret.x[1] = (6 - a.x[1] - b.x[1]) % 3;
ret.x[2] = (6 - a.x[2] - b.x[2]) % 3;
ret.num = ret.x[0] + ret.x[1] * 3 + ret.x[2] * 9;
//cout << ret.x[0] << ' ' << ret.x[1] << ' ' << ret.x[2] << ' ' << ret.num << endl;
return ret;
}
void shift(int, int, int);
void build(int l, int r, int v){
if(r - l == 1){
hsh[v].fi = t[l] * pw[0][n - l - 1] % mod[1];
hsh[v].se = t[l] * pw[1][n - l - 1] % mod[0];
return;
}
int mid = (l + r) >> 1;
build(l, mid, v * 2);
build(mid, r, v * 2 + 1);
hsh[v].fi = (hsh[v * 2].fi + hsh[v * 2 + 1].fi) % mod[0];
hsh[v].se = (hsh[v * 2].se + hsh[v * 2 + 1].se) % mod[1];
}
void upd(int l, int r, int lq, int rq, int val, int v){
if(rq <= l || r <= lq)
return;
if(lq <= l && r <= rq){
lazy[v] = val;
hsh[v].fi = (mod[0] + ps[0][n - l - 1] - (r == n ? 0 : ps[0][n - r - 1])) % mod[0] * val % mod[0];
hsh[v].se = (mod[1] + ps[1][n - l - 1] - (r == n ? 0 : ps[1][n - r - 1])) % mod[1] * val % mod[1];
return;
}
int mid = (l + r) >> 1;
shift(l, r, v);
upd(l, mid, lq, rq, val, v * 2);
upd(mid, r, lq, rq, val, v * 2 + 1);
hsh[v].fi = (hsh[v * 2].fi + hsh[v * 2 + 1].fi) % mod[0];
hsh[v].se = (hsh[v * 2].se + hsh[v * 2 + 1].se) % mod[1];
}
void shift(int l, int r, int v){
if(lazy[v] == -1)
return;
int mid = (l + r) >> 1;
upd(l, mid, l, mid, lazy[v], v * 2);
upd(mid, r, mid, r, lazy[v], v * 2 + 1);
lazy[v] = -1;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
memset(lazy, -1, sizeof lazy);
cin >> n;
cin >> s[0] >> s[1] >> s[2];
for(int tt = 0; tt < 2; tt++){
pw[tt][0] = 1;
for(int i = 1; i < maxn5; i++)
pw[tt][i] = (pw[tt][i - 1] * base[tt]) % mod[tt];
ps[tt][0] = 1;
for(int i = 1; i < maxn5; i++)
ps[tt][i] = (ps[tt][i - 1] + pw[tt][i]) % mod[tt];
}
zarib a, b, c;
a.x[0] = b.x[1] = c.x[2] = 1;
a.num = 1;
b.num = 3;
c.num = 9;
q[0] = a;
q[1] = b;
q[2] = c;
int l = 0, r = 3;
while(l < r){
zarib a = q[l];
for(int i = 0; i < l; i++){
zarib x = comb(a, q[i]);
if(!mark[x.num]){
q[r++] = x;
mark[x.num] = true;
}
}
l++;
}
for(int i = 0; i < r; i++){
ll val[2] = {0, 0};
for(int j = 0; j < n; j++){
int a = (get_val(s[0][j]) * q[i].x[0] + get_val(s[1][j]) * q[i].x[1] + get_val(s[2][j]) * q[i].x[2]) % 3;
val[0] = (val[0] * base[0] + a) % mod[0];
val[1] = (val[1] * base[1] + a) % mod[1];
}
//cout << i << ' ' << val[0] << ' ' << val[1] << endl;
av.insert(mp(val[0], val[1]));
}
string tm; int q;
cin >> q >> tm;
for(int i = 0; i < n; i++)
t[i] = get_val(tm[i]);
build(0, n, 1);
//cout << hsh[1].fi << ' ' << hsh[1].se << endl;
cout << (av.find(hsh[1]) != av.end() ? "Yes\n" : "No\n");
while(q--){
int l, r; char c; cin >> l >> r >> c;
int a = get_val(c);
upd(0, n, l - 1, r, a, 1);
cout << (av.find(hsh[1]) != av.end() ? "Yes\n" : "No\n");
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
12376 KB |
Output is correct |
| 2 |
Correct |
92 ms |
12580 KB |
Output is correct |
| 3 |
Correct |
98 ms |
12412 KB |
Output is correct |
| 4 |
Incorrect |
75 ms |
12520 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
12376 KB |
Output is correct |
| 2 |
Correct |
92 ms |
12580 KB |
Output is correct |
| 3 |
Correct |
98 ms |
12412 KB |
Output is correct |
| 4 |
Incorrect |
75 ms |
12520 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
12376 KB |
Output is correct |
| 2 |
Correct |
92 ms |
12580 KB |
Output is correct |
| 3 |
Correct |
98 ms |
12412 KB |
Output is correct |
| 4 |
Incorrect |
75 ms |
12520 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
12376 KB |
Output is correct |
| 2 |
Correct |
92 ms |
12580 KB |
Output is correct |
| 3 |
Correct |
98 ms |
12412 KB |
Output is correct |
| 4 |
Incorrect |
75 ms |
12520 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
