#include <bits/stdc++.h>
using namespace std;
struct Query {
int l, r, c;
};
int get_id(char c) {
if (c == 'J') return 0;
if (c == 'O') return 1;
if (c == 'I') return 2;
assert(0);
return -1;
}
vector<int> read(int n) {
string s;
cin >> s;
vector<int> res(n);
for (int i = 0; i < n; ++i) res[i] = get_id(s[i]);
return res;
}
int n, q;
vector<vector<int>> strs;
vector<int> t;
vector<Query> queries;
vector<vector<int>> pref;
set<pair<pair<int, int>, int>> st;
int cnt_good;
vector<int> vec_add(vector<int> a, vector<int> b) {
vector<int> res(n);
for (int i = 0; i < n; ++i) res[i] = (6 + -a[i] - b[i]) % 3;
return res;
}
bool check(int l, int r, int c) {
return pref[r][c] - pref[l][c] == r - l;
}
void insert(int l, int r, int c) {
st.insert({{l, r}, c});
if (check(l, r, c)) ++cnt_good;
}
void erase(int l, int r, int c) {
st.erase({{l, r}, c});
if (check(l, r, c)) --cnt_good;
}
bool all_good() {
return cnt_good == (int)st.size();
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 0; i < 3; ++i) strs.push_back(read(n));
{
bool was = 1;
while (was) {
/*for (auto s : strs) {
for (auto c : s) cout << c;
cout << endl;
}*/
was = 0;
vector<vector<int>> added;
for (auto s1 : strs) {
for (auto s2 : strs) {
auto cur = vec_add(s1, s2);
bool has = 0;
for (auto s : strs) has |= cur == s;
if (!has) {
added.push_back(cur);
was = 1;
}
}
}
for (auto s : added) strs.push_back(s);
}
}
cin >> q;
t = read(n);
queries.resize(q);
for (int i = 0; i < q; ++i) {
cin >> queries[i].l >> queries[i].r;
--queries[i].l;
char c;
cin >> c;
queries[i].c = get_id(c);
}
vector<int> ans(q + 1, 0);
for (auto s : strs) {
pref.assign(n + 1, vector<int>(3, 0));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 3; ++j) pref[i + 1][j] = pref[i][j] + (s[i] == j);
}
st = {};
cnt_good = 0;
for (int i = 0; i < n; ++i) insert(i, i + 1, t[i]);
for (int i = 0; i <= q; ++i) {
ans[i] |= all_good();
if (i != q) {
int l = queries[i].l, r = queries[i].r, c = queries[i].c;
vector<pair<pair<int, int>, int>> inserted, erased;
auto it = st.lower_bound({{l, -1}, -1});
if (it != st.begin()) --it;
for (int iteration = 0; it != st.end(); ++iteration, ++it) {
int curl = it->first.first, curr = it->first.second, curc = it->second;
if (iteration != 0 && (curl >= r || curr <= l)) break;
if (curl >= r || curr <= l) continue;
int cl = max(curl, l), cr = min(curr, r);
erased.push_back({{curl, curr}, curc});
inserted.push_back({{cl, cr}, c});
inserted.push_back({{curl, cl}, curc});
inserted.push_back({{curr, cr}, curc});
}
for (auto seg : erased) erase(seg.first.first, seg.first.second, seg.second);
for (auto seg : inserted) {
if (seg.first.first < seg.first.second) insert(seg.first.first, seg.first.second, seg.second);
}
}
}
}
for (int i = 0; i <= q; ++i) cout << (ans[i] ? "Yes\n" : "No\n");
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2350 ms |
3708 KB |
Output is correct |
| 2 |
Correct |
2975 ms |
4036 KB |
Output is correct |
| 3 |
Execution timed out |
7091 ms |
3424 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2350 ms |
3708 KB |
Output is correct |
| 2 |
Correct |
2975 ms |
4036 KB |
Output is correct |
| 3 |
Execution timed out |
7091 ms |
3424 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2350 ms |
3708 KB |
Output is correct |
| 2 |
Correct |
2975 ms |
4036 KB |
Output is correct |
| 3 |
Execution timed out |
7091 ms |
3424 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2350 ms |
3708 KB |
Output is correct |
| 2 |
Correct |
2975 ms |
4036 KB |
Output is correct |
| 3 |
Execution timed out |
7091 ms |
3424 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
