#include <bits/stdc++.h>
using namespace std;
vector<string> s(3);
vector<long long> hash_val(9);
string q;
long long c[(int)2e5+1], cc[(int)(2e5+2)];
const int mod=998244353;
void get(string &a, string &b){
string res;
int n=a.size();
for (int i=0; i<n; i++){
if (a[i] == b[i]){
res += a[i]; continue;
}
if (a[i] == 'J'){
if (b[i] == 'O'){res += 'I';}
else{res += 'O';}
}else if (a[i] == 'O'){
if (b[i] == 'J'){res += 'I';}
else{res += 'J';}
}else{
if (b[i] == 'J'){res += 'O';}
else{res += 'J';}
}
}
s.push_back(res);
}
long long get_hash(string &a){
int n=a.size();
long long res=0;
for (int i=0; i<n; i++){
res += c[i] * (a[i]-'A');
res %= mod;
}
return res;
}
struct segTree{
int l, r, mid;
long long val, lz=0;
segTree *tl, *tr;
segTree(int ll, int rr): l(ll), r(rr){
mid = (l+r)/2;
if (l == r-1){
val = c[l] * (q[l]-'A');
return;
}
tl = new segTree(l, mid);
tr = new segTree(mid, r);
val = (tl->val + tr->val) % mod;
}
void push(){
if (lz == 0){return;}
if (l == r-1){
val = c[l] * lz % mod; lz = 0;
return;
}
tl->val = lz * (cc[mid] - cc[l]) % mod;
tr->val = lz * (cc[r] - cc[mid]) % mod;
tl->lz = lz; tr->lz = lz;
lz = 0;
}
void update(int ll, int rr, long long u){
if (ll <= l && rr >= r){
lz = u;
val = u * (cc[r] - cc[l]);
val %= mod;
if (val < 0){val += mod;}
return;
}
push();
if (ll < mid){tl->update(ll, rr, u);}
if (mid < rr){tr->update(ll, rr, u);}
val = tl->val + tr->val;
}
};
int main(){
cin.sync_with_stdio(0); cin.tie(0);
int len; cin >> len;
for (int i=0; i<3; i++){cin >> s[i];}
get(s[0], s[1]); get(s[1], s[2]); get(s[2], s[0]);
get(s[3], s[2]); get(s[4], s[0]); get(s[5], s[1]);
c[0] = 1;
for (int i=1; i<2e5+1; i++){
c[i] = c[i-1] * 29;
c[i] %= mod;
}
cc[0] = 0;
for (int i=1; i<2e5+2; i++){
cc[i] = cc[i-1] + c[i-1];
cc[i] %= mod;
}
for (int i=0; i<9; i++){
hash_val[i] = get_hash(s[i]);
}
int n; cin >> n;
cin >> q;
segTree st(0, len);
bool check=0;
for (auto v: hash_val){
if (v == st.val){check = 1; break;}
}
cout << ((check)? "Yes": "No") << '\n';
for (int nn=0; nn<n; nn++){
int l, r; char m; cin >> l >> r >> m;
int x=m-'A'; l--;
st.update(l, r, x);
check = 0;
for (auto v: hash_val){
if (v == st.val){check = 1; break;}
}
cout << ((check)? "Yes": "No") << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
3944 KB |
Output is correct |
| 2 |
Correct |
64 ms |
4016 KB |
Output is correct |
| 3 |
Correct |
60 ms |
4044 KB |
Output is correct |
| 4 |
Incorrect |
55 ms |
4028 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
3944 KB |
Output is correct |
| 2 |
Correct |
64 ms |
4016 KB |
Output is correct |
| 3 |
Correct |
60 ms |
4044 KB |
Output is correct |
| 4 |
Incorrect |
55 ms |
4028 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
3944 KB |
Output is correct |
| 2 |
Correct |
64 ms |
4016 KB |
Output is correct |
| 3 |
Correct |
60 ms |
4044 KB |
Output is correct |
| 4 |
Incorrect |
55 ms |
4028 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
3944 KB |
Output is correct |
| 2 |
Correct |
64 ms |
4016 KB |
Output is correct |
| 3 |
Correct |
60 ms |
4044 KB |
Output is correct |
| 4 |
Incorrect |
55 ms |
4028 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
