#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
const int mod = 1e9 + 7;
const int mxN = 2e5 + 5;
int p[mxN];
int pp[mxN];
vector<string> v;
vector<int> hsh;
int t[4 * mxN];
int lazy[4 * mxN];
int sz;
int eval(char c) {
if (c == 'I') return 0;
if (c == 'O') return 1;
return 2;
}
void hashh(string s) {
hsh.push_back(0);
for (char c : s) {
hsh.back() = (3LL * hsh.back() + eval(c)) % mod;
}
}
void build(int x, int lx, int rx) {
if (lx == rx) {
t[x] = eval(v[sz - 1][lx - 1]);
lazy[x] = -1;
return;
}
int mx = (lx + rx) >> 1;
build(x << 1, lx, mx);
build(x << 1 | 1, mx + 1, rx);
lazy[x] = -1;
t[x] = ((t[x << 1] * p[rx - mx]) % mod + t[x << 1 | 1]) % mod;
}
int calc(int c, int len) {
return (pp[len - 1] * c) % mod;
}
void propagate(int x, int lx, int rx) {
if (lx == rx) return;
int mx = (lx + rx) >> 1;
t[x << 1] = calc(lazy[x], mx - lx + 1);
t[x << 1 | 1] = calc(lazy[x], rx - mx);
lazy[x << 1] = lazy[x << 1 | 1] = lazy[x];
lazy[x] = -1;
return;
}
void update(int x, int lx, int rx, int l, int r, int c) {
if (lazy[x] != -1) propagate(x, lx, rx);
if (l > rx || lx > r) return;
if (l <= lx && r >= rx) {
t[x] = calc(c, rx - lx + 1);
lazy[x] = c;
return;
}
int mx = (lx + rx) >> 1;
update(x << 1, lx, mx, l, r, c);
update(x << 1 | 1, mx + 1, rx, l, r, c);
t[x] = ((t[x << 1] * p[rx - mx]) % mod + t[x << 1 | 1]) % mod;
}
void init(string a, string b, string c) {
p[0] = 1;
for (int i = 1; i < mxN; i++) p[i] = (3LL * p[i - 1]) % mod;
pp[0] = 1;
for (int i = 1; i < mxN; i++) pp[i] = (pp[i - 1] + p[i]) % mod;
map<string, bool> mp;
v = {a, b, c};
mp[a] = mp[b] = mp[c] = true;
auto op = [&](string s, string tt) {
string ret;
for (int i = 0; i < (int) s.size(); i++) {
if (s[i] == tt[i]) ret += s[i];
else ret += ('I' ^ 'J' ^ 'O') ^ s[i] ^ tt[i];
}
return ret;
};
for (int i = 0; i < (int) v.size(); i++) {
for (int j = i + 1; j < (int) v.size(); j++) {
string ops = op(v[i], v[j]);
if (!mp[ops]) {
mp[ops] = true;
v.push_back(ops);
}
}
}
for (string s : v) {
hashh(s);
}
sz = v.size() + 1;
}
void query() {
// cout << t[1] << endl;
for (int i : hsh) {
if (i == t[1]) {
cout << "Yes\n";
return;
}
}
cout << "No\n";
}
void testCase() {
int n;
string a, b, c;
cin >> n >> a >> b >> c;
init(a, b, c);
int q;
string tt;
cin >> q >> tt;
v.push_back(tt);
build(1, 1, n);
query();
// for (string s : v) cout << s << " "; cout << endl;
// for (int i : hsh) cout << i << " "; cout << endl;
while (q--) {
int l, r;
char cc;
cin >> l >> r >> cc;
update(1, 1, n, l, r, eval(cc));
query();
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
testCase();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
2416 KB |
Output is correct |
| 2 |
Correct |
76 ms |
3912 KB |
Output is correct |
| 3 |
Correct |
79 ms |
3832 KB |
Output is correct |
| 4 |
Incorrect |
63 ms |
3928 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
2416 KB |
Output is correct |
| 2 |
Correct |
76 ms |
3912 KB |
Output is correct |
| 3 |
Correct |
79 ms |
3832 KB |
Output is correct |
| 4 |
Incorrect |
63 ms |
3928 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
2416 KB |
Output is correct |
| 2 |
Correct |
76 ms |
3912 KB |
Output is correct |
| 3 |
Correct |
79 ms |
3832 KB |
Output is correct |
| 4 |
Incorrect |
63 ms |
3928 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
2416 KB |
Output is correct |
| 2 |
Correct |
76 ms |
3912 KB |
Output is correct |
| 3 |
Correct |
79 ms |
3832 KB |
Output is correct |
| 4 |
Incorrect |
63 ms |
3928 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
