#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;
const vector<vector<int>> coefs = {{0, 0, 1},
{0, 1, 0},
{1, 0, 0},
{0, 2, 2},
{2, 0, 2},
{0, 2, 2},
{2, 2, 0},
{2, 0, 2},
{2, 2, 0},
{1, 1, 2},
{1, 1, 2},
{1, 2, 1},
{1, 2, 1},
{2, 1, 1},
{2, 1, 1},
{2, 1, 1},
{1, 1, 2},
{1, 2, 1},
{1, 1, 2},
{1, 2, 1},
{1, 2, 1},
{1, 1, 2},
{1, 1, 2},
{2, 1, 1},
{2, 1, 1},
{2, 1, 1},
{1, 1, 2},
{1, 2, 1},
{1, 1, 2},
{1, 2, 1},
{1, 1, 2},
{1, 2, 1},
{2, 1, 1},
{1, 2, 1},
{2, 1, 1},
{1, 2, 1},
{1, 1, 2},
{1, 1, 2},
{2, 1, 1},
{2, 1, 1},
{1, 1, 2},
{1, 2, 1},
{2, 1, 1},
{1, 2, 1},
{2, 1, 1}};
vector<int> str_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;
}
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));
{
vector<vector<int>> nstrs;
for (auto v : coefs) {
vector<int> cur(n);
for (int i = 0; i < n; ++i) cur[i] = (strs[0][i] * v[0] + strs[1][i] * v[1] + strs[2][i] * v[2]) % 3;
nstrs.push_back(cur);
}
strs = nstrs;
}
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] |= cnt_good == (int)st.size();
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 (curl >= r || curr <= l) {
if (iteration == 0) {
continue;
} else {
break;
}
}
int cl = max(curl, l), cr = min(curr, r);
erased.push_back({{curl, curr}, curc});
inserted.push_back({{curl, cl}, curc});
inserted.push_back({{cl, cr}, c});
inserted.push_back({{cr, curr}, curc});
}
for (auto seg : erased) erase(seg.first.first, seg.first.second, seg.second);
{
vector<pair<pair<int, int>, int>> compressed;
for (auto seg : inserted) {
int curl = seg.first.first, curr = seg.first.second, curc = seg.second;
if (curl >= curr) continue;
if (compressed.empty() || curl > compressed.back().first.second || curc != compressed.back().second) {
compressed.push_back({{curl, curr}, curc});
} else {
compressed.back().first.second = curr;
}
}
inserted = compressed;
}
for (auto seg : inserted) 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 |
6453 ms |
3764 KB |
Output is correct |
| 2 |
Correct |
6906 ms |
3996 KB |
Output is correct |
| 3 |
Correct |
5400 ms |
3988 KB |
Output is correct |
| 4 |
Execution timed out |
7016 ms |
3268 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6453 ms |
3764 KB |
Output is correct |
| 2 |
Correct |
6906 ms |
3996 KB |
Output is correct |
| 3 |
Correct |
5400 ms |
3988 KB |
Output is correct |
| 4 |
Execution timed out |
7016 ms |
3268 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6453 ms |
3764 KB |
Output is correct |
| 2 |
Correct |
6906 ms |
3996 KB |
Output is correct |
| 3 |
Correct |
5400 ms |
3988 KB |
Output is correct |
| 4 |
Execution timed out |
7016 ms |
3268 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6453 ms |
3764 KB |
Output is correct |
| 2 |
Correct |
6906 ms |
3996 KB |
Output is correct |
| 3 |
Correct |
5400 ms |
3988 KB |
Output is correct |
| 4 |
Execution timed out |
7016 ms |
3268 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
