#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;
struct node {
int sc, tc, val, tag;
} seg[maxn * 4];
void build(int id, int l, int r, vector<int> &v, vector<int> &t) {
seg[id].sc = seg[id].tc = seg[id].tag = -1;
seg[id].val = 0;
if (l == r-1) {
seg[id].sc = v[l];
seg[id].tc = t[l];
seg[id].val = (v[l] == t[l]);
seg[id].tag = -1;
return;
}
int mid = l + r >> 1;
build(id * 2 + 1, l, mid, v, t);
build(id * 2 + 2, mid, r, v, t);
seg[id].sc = (seg[id * 2 + 1].sc == seg[id * 2 + 2].sc ? seg[id * 2 + 1].sc : -1);
seg[id].tc = (seg[id * 2 + 1].tc == seg[id * 2 + 2].tc ? seg[id * 2 + 1].tc : -1);
seg[id].val = seg[id * 2 + 1].val & seg[id * 2 + 2].val;
}
void push(int id) {
if (seg[id].tag == -1) return;
seg[id * 2 + 1].tag = seg[id].tag;
seg[id * 2 + 2].tag = seg[id].tag;
seg[id].tag = -1;
}
void ins(int id, int l, int r, int L, int R, int op) {
if (L <= l && R >= r) {
seg[id].tag = op;
seg[id].tc = op;
seg[id].val = (seg[id].tc == seg[id].sc);
return;
}
int mid = l + r >> 1;
push(id);
ins(id * 2 + 1, l, mid, L, R, op);
ins(id * 2 + 2, mid, r, L, R, op);
int lc = (seg[id * 2 + 1].tag == -1 ? seg[id * 2 + 1].tc : seg[id * 2 + 1].tag);
int rc = (seg[id * 2 + 2].tag == -1 ? seg[id * 2 + 2].tc : seg[id * 2 + 2].tag);
int lval = (seg[id * 2 + 1].tag == -1 ? seg[id * 2 + 1].val : (seg[id * 2 + 1].tag == seg[id * 2 + 1].sc));
int rval = (seg[id * 2 + 2].tag == -1 ? seg[id * 2 + 2].val : (seg[id * 2 + 2].tag == seg[id * 2 + 2].sc));
seg[id].tc = (lc == rc ? lc : -1);
seg[id].val = lval & rval;
}
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] |= 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;
ins(0, 0, n, l, r, op);
ans[i+1] |= seg[0].val;
}
};
for (auto vec : G) {
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:32:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
32 | 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:54:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
54 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
38 ms |
33624 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
38 ms |
33624 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
38 ms |
33624 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
38 ms |
33624 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
