#include <bits/stdc++.h>
using i64 = long long;
int pre[9][3][200005];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
auto in = [&]() {
std::string a;
std::cin >> a;
std::vector<int> b(n);
for (int i = 0; i < n; i++) {
b[i] = std::string("JOI").find(a[i]);
}
return b;
};
std::vector<int> a = in(), b = in(), c = in();
auto merge = [&](std::vector<int> a, std::vector<int> b) {
auto c = a;
for (int i = 0; i < n; i++) {
if (a[i] != b[i]) {
c[i] = 0 ^ 1 ^ 2 ^ a[i] ^ b[i];
}
}
return c;
};
std::vector<std::vector<int>> s{a, b, c, merge(a, b), merge(a, c), merge(b, c), merge(merge(a, c), b), merge(merge(a, b), c), merge(merge(b, c), a)};
int q;
std::cin >> q;
std::vector<int> t = in();
for (int k = 0; k < 9; k++) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < n; j++) {
pre[k][i][j + 1] = pre[k][i][j] + (s[k][j] == i);
}
}
}
bool bad[9] {};
for (int k = 0; k < 9; k++) {
for (int i = 0; i < n; i++) {
bad[k] += t[i] != s[k][i];
}
}
std::set<std::pair<int, int>> p{{-1, -1}, {n, -1}};
for (int i = 0; i < n; i++)
p.emplace(i, t[i]);
bool ok = false;
for (int k = 0; k < 9; k++) {
ok |= bad[k] == 0;
}
if (ok) {
std::cout << "Yes\n";
} else {
std::cout << "No\n";
}
auto rem = [&](int l, int r, int c) {
for (int k = 0; k < 9; k++) {
bad[k] -= pre[k][c][r] - pre[k][c][l] != r - l;
}
};
auto add = [&](int l, int r, int c) {
for (int k = 0; k < 9; k++) {
bad[k] += pre[k][c][r] - pre[k][c][l] != r - l;
}
};
while (q--) {
int l, r;
char ch;
std::cin >> l >> r >> ch;
l--;
int x = std::string("JOI").find(ch);
auto it = p.lower_bound({l, 0});
if (it->first > l) {
int L = std::prev(it)->first;
int R = it->first;
int c = std::prev(it)->second;
rem(L, R, c);
add(L, l, c);
add(l, R, c);
p.emplace(l, c);
}
it = p.lower_bound({r, 0});
if (std::prev(it)->first < r - 1) {
int L = std::prev(it)->first;
int R = it->first;
int c = std::prev(it)->second;
rem(L, R, c);
add(L, r, c);
add(r, R, c);
p.emplace(r, c);
}
while (true) {
it = p.lower_bound({l, 0});
if (it->first < r) {
rem(it->first, std::next(it)->first, it->second);
p.erase(it);
} else {
break;
}
}
add(l, r, x);
p.emplace(l, x);
bool ok = false;
for (int k = 0; k < 9; k++) {
ok |= bad[k] == 0;
}
if (ok) {
std::cout << "Yes\n";
} else {
std::cout << "No\n";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
121 ms |
2268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
121 ms |
2268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
121 ms |
2268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
121 ms |
2268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
