#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7, BASE = 5, MXN = 2e5+5;
ll Pow[MXN], Same[MXN];
ll getVal(char c) {
if (c == 'J') return 1;
if (c == 'O') return 2;
return 3;
}
char cross(char a, char b) {
if (a == b) return a;
if (a != 'O' && b != 'O') return 'O';
if (a != 'J' && b != 'J') return 'J';
return 'I';
}
string merge(string a, string b) {
string c(a.size(), ' ');
for (int i = 0; i<a.size(); ++i) {
c[i] = cross(a[i], b[i]);
}
return c;
}
vector<ll> starter;
struct Node {
ll l,r, mid,sz, set, hash;
Node *lp, *rp;
void blaSet(ll val) {
hash = val * Same[sz-1];
set = val;
}
void pull() {
hash = lp->hash * Pow[lp->sz] + rp->hash;
hash %= MOD;
}
void push() {
if (set != -1) {
lp->blaSet(set), rp->blaSet(set);
set = -1;
}
}
Node(ll l, ll r) : l(l), r(r), mid((l+r)/2), sz(r-l+1), set(-1) {
if (l != r) {
lp = new Node(l, mid), rp = new Node(mid+1,r);
pull();
}
else blaSet(starter[l]);
}
void update(int s, int e, ll val) {
if (s > r || e < l) return;
if (s <= l && e >= r) {
blaSet(val);
return;
}
if (s <= mid) lp->update(s,e,val);
if (e > mid) rp->update(s,e,val);
pull();
}
};
void init() {
Pow[0] = 1; Same[0] = 1;
for (int i = 1; i<MXN; ++i) {
Pow[i] = (Pow[i-1] * BASE) % MOD;
Same[i] = (Same[i-1] * BASE + 1) % MOD;
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n,q; cin >> n;
init();
vector<string> start(3);
set<string> s;
for (string &S :start) {
cin >> S;
s.insert(S);
}
/*for (int i = 0; i<3; ++i) for (int j = i+1; j<3; ++j) s.insert(merge(start[i], start[j]));
s.insert(merge(start[0], merge(start[2], start[1])));
s.insert(merge(start[1], merge(start[2], start[0])));
s.insert(merge(start[2], merge(start[1], start[0])));
*/
ll tot = 0;
for (int i = 0; i<n; ++i) tot = (tot*BASE + getVal(start[0][i])) % MOD;
cin >> q;
string seq; cin >> seq;
cout << (s.count(seq) ? "Yes" : "No") << '\n';
starter.resize(n);
for (int i = 0; i<n; ++i) starter[i] = getVal(seq[i]);
Node *seg = new Node(0, n-1);
while (q--) {
int l,r; char c;
cin >> l >> r >> c;
ll ne = getVal(c);
seg->update(l-1,r-1,ne);
cout << (seg->hash == tot ? "Yes" : "No") << '\n';
}
}
Compilation message
Main.cpp: In function 'std::string merge(std::string, std::string)':
Main.cpp:20:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for (int i = 0; i<a.size(); ++i) {
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
3932 KB |
Output is correct |
| 2 |
Correct |
38 ms |
4180 KB |
Output is correct |
| 3 |
Correct |
35 ms |
4168 KB |
Output is correct |
| 4 |
Incorrect |
33 ms |
3928 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
3932 KB |
Output is correct |
| 2 |
Correct |
38 ms |
4180 KB |
Output is correct |
| 3 |
Correct |
35 ms |
4168 KB |
Output is correct |
| 4 |
Incorrect |
33 ms |
3928 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
3932 KB |
Output is correct |
| 2 |
Correct |
38 ms |
4180 KB |
Output is correct |
| 3 |
Correct |
35 ms |
4168 KB |
Output is correct |
| 4 |
Incorrect |
33 ms |
3928 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
3932 KB |
Output is correct |
| 2 |
Correct |
38 ms |
4180 KB |
Output is correct |
| 3 |
Correct |
35 ms |
4168 KB |
Output is correct |
| 4 |
Incorrect |
33 ms |
3928 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
