#ifndef Yamada
#define Yamada
#include Yamada __FILE__ Yamada
char JOI[] = {'J', 'O', 'I'};
vector<int> cross(vector<int> &g1, vector<int> &g2) {
vector<int> ret;
for (int i = 0; i < SZ(g1); ++i) {
int cur = 2 * (g1[i] + g2[i]) % 3;
ret.eb(cur);
}
return ret;
}
const int maxn = 2e5 + 5;
int sc[maxn * 4];
struct S {
int c, val, id;
S() : c(-1), val(0), id(-1) {}
S(int _c, int _val, int _id) : c(_c), val(_val), id(_id) {}
};
struct F {
int c;
F() : c(-1) {}
F(int _c) : c(_c) {}
};
S seg[maxn * 4];
F tag[maxn * 4];
S opr(S l, S r) {
int c, val;
if (l.c == -1 || r.c == -1) c = -1;
else if (l.c == r.c) c = l.c;
else c = -1;
val = l.val & r.val;
return S(c, val, (l.id - 1) / 2);
}
S M(F f, S s) {
if (f.c == -1) return s;
s.c = f.c;
s.val = (sc[s.id] == s.c);
return s;
}
F comp(F l, F r) { // first l, second r
return r;
}
void build(int id, int l, int r, vector<int> &v, vector<int> &t) {
tag[id] = F();
if (l == r-1) {
sc[id] = v[l];
seg[id] = S(t[l], (t[l] == v[l]), id);
debug(l, sc[id], t[l]);
for (int i = 0; i < SZ(v); ++i) {
debug(v[i]);
}
return;
}
int mid = l + r >> 1;
build(id * 2 + 1, l, mid, v, t);
build(id * 2 + 2, mid, r, v, t);
seg[id] = opr(seg[id * 2 + 1], seg[id * 2 + 2]);
sc[id] = (sc[id * 2 + 1] == sc[id * 2 + 2] ? sc[id * 2 + 1] : -1);
}
void ins(int id, int l, int r, int L, int R, int op) {
// debug(l, r, id, tag[id].c, tag[3].c);
if (L <= l && r <= R) {
// debug(l, r, id);
tag[id] = comp(tag[id], F(op));
seg[id] = M(tag[id], seg[id]);
// debug(id, seg[id].c, l, r, seg[id-1].c, tag[id-1].c, M(tag[id-1], seg[id-1]).c);
return;
}
if (r <= L || l >= R) return;
int mid = l + r >> 1;
tag[id * 2 + 1] = comp(tag[id * 2 + 1], tag[id]);
tag[id * 2 + 2] = comp(tag[id * 2 + 2], tag[id]);
seg[id * 2 + 1] = M(tag[id * 2 + 1], seg[id * 2 + 1]);
seg[id * 2 + 2] = M(tag[id * 2 + 2], seg[id * 2 + 2]);
// debug(id, tag[id].c, l, r);
seg[id] = M(tag[id], seg[id]);
// debug(id);
tag[id] = F();
ins(id * 2 + 1, l, mid, L, R, op);
ins(id * 2 + 2, mid, r, L, R, op);
seg[id] = opr(
M(tag[id * 2 + 1], seg[id * 2 + 1]),
M(tag[id * 2 + 2], seg[id * 2 + 2])
);
// debug(id, l, r, L, R, op, seg[id].val, sc[id], seg[id].c, tag[id].c);
}
void solve() {
int n; cin >> n;
vector<int> gene[3];
for (int i = 0; i < 3; ++i) {
string s; cin >> s;
for (int j = 0; j < n; ++j) {
for (int k = 0; k < 3; ++k) {
if (s[j] == JOI[k]) gene[i].eb(k);
}
}
}
vector<vector<int>> G;
G.eb(gene[0]);
G.eb(gene[1]);
G.eb(gene[2]);
vector<int> t1 = cross(gene[0], gene[1]);
vector<int> t2 = cross(gene[0], gene[2]);
vector<int> t3 = cross(gene[1], gene[2]);
G.eb(t1);
G.eb(t2);
G.eb(t3);
G.eb(cross(t1, gene[2]));
G.eb(cross(t2, gene[1]));
G.eb(cross(t3, gene[0]));
int q; cin >> q;
string T; cin >> T;
vector<int> gt;
for (int i = 0; i < n; ++i) {
for (int k = 0; k < 3; ++k) {
if (T[i] == JOI[k]) gt.eb(k);
}
}
vector<pair<pii, int>> qr;
for (int i = 1; i <= q; ++i) {
int l, r;
cin >> l >> r;
--l;
char c; cin >> c;
int op = -1;
for (int k = 0; k < 3; ++k) if (c == JOI[k]) op = k;
qr.eb(pii(l, r), op);
}
vector<int> ans(q + 1);
auto cal = [&](vector<int> &v) -> void {
build(0, 0, n, v, gt);
ans[0] |= M(tag[0], seg[0]).val;
for (int i = 0; i < q; ++i){
int l = qr[i].X.X, r = qr[i].X.Y, op = qr[i].Y;
debug(tag[3].c);
ins(0, 0, n, l, r, op);
S val = M(tag[0], seg[0]);
debug(val.c, val.val, val.id);
ans[i+1] |= val.val;
}
};
for (auto vec : G) {
debug("ALIVE");
for (auto it : vec) debug(it);
cal(vec);
}
for (int i = 0; i <= q; ++i) {
if (ans[i]) print("Yes");
else print("No");
}
}
signed main() {
IOS();
int t = 1; // cin >> t;
for (int i=1;i<=t;++i) solve();
return 0;
}
#else
#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize ("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define double __float80
using pii = pair<int, int>;
template <typename T> using MaxHeap = std::priority_queue<T>;
template <typename T> using MinHeap = std::priority_queue<T, vector<T>, greater<T>>;
#define SZ(a) ((int)(a).size())
#define ALL(a) begin(a), end(a)
#define RALL(a) rbegin(a), rend(a)
#define ee emplace
#define eb emplace_back
#define ef emplace_front
#define pb pop_back
#define pf pop_front
#define X first
#define Y second
#ifdef local
#define IOS() void()
#define debug(...) \
fprintf(stderr, "\e[1;93m"), \
fprintf(stderr, "At [%s], line %d: (%s) = ", __FUNCTION__, __LINE__, #__VA_ARGS__), \
_do(__VA_ARGS__), \
fprintf(stderr, "\e[0m")
template <typename T> void _do(T &&_t) {cerr << _t << '\n';}
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) {cerr << _t << ", ", _do(_u...);}
#define print(...) \
fprintf(stderr, "\e[1;96m"), \
_P(__VA_ARGS__), \
fprintf(stderr, "\e[0m")
#else
#define IOS() ios_base::sync_with_stdio(0); cin.tie(0)
#define debug(...) void()
#define print(...) _P(__VA_ARGS__)
#define endl '\n'
#endif
template <typename U, typename V> bool chmin(U &u, V v) {return u > v ? u = v, 1 : 0;}
template <typename U, typename V> bool chmax(U &u, V v) {return u < v ? u = v, 1 : 0;}
template <typename T> void _P(T &&_x) {cout << _x << '\n';}
template <typename T, typename ...S> void _P(T &&_x, S &&..._t) {cout << _x << " "; _P(_t...);}
#endif
Compilation message
Main.cpp: In function 'void build(int64_t, int64_t, int64_t, std::vector<long int>&, std::vector<long int>&)':
Main.cpp:65:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | int mid = l + r >> 1;
| ~~^~~
Main.cpp: In function 'void ins(int64_t, int64_t, int64_t, int64_t, int64_t, int64_t)':
Main.cpp:82:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
82 | int mid = l + r >> 1;
| ~~^~~
Main.cpp: In function 'void solve()':
Main.cpp:159:19: warning: unused variable 'it' [-Wunused-variable]
159 | for (auto it : vec) debug(it);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
241 ms |
35132 KB |
Output is correct |
| 2 |
Correct |
286 ms |
34740 KB |
Output is correct |
| 3 |
Correct |
275 ms |
35536 KB |
Output is correct |
| 4 |
Incorrect |
227 ms |
34504 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
241 ms |
35132 KB |
Output is correct |
| 2 |
Correct |
286 ms |
34740 KB |
Output is correct |
| 3 |
Correct |
275 ms |
35536 KB |
Output is correct |
| 4 |
Incorrect |
227 ms |
34504 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
241 ms |
35132 KB |
Output is correct |
| 2 |
Correct |
286 ms |
34740 KB |
Output is correct |
| 3 |
Correct |
275 ms |
35536 KB |
Output is correct |
| 4 |
Incorrect |
227 ms |
34504 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
241 ms |
35132 KB |
Output is correct |
| 2 |
Correct |
286 ms |
34740 KB |
Output is correct |
| 3 |
Correct |
275 ms |
35536 KB |
Output is correct |
| 4 |
Incorrect |
227 ms |
34504 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
