#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define int long long
#define hash uhasfsfjha
const int nmax = 2e5 + 5;
const int mod = 998244353;
int p[2][nmax];
struct hash {
int v[2] = {0, 0};
int len = 0;
hash() {;}
hash(int ch) {v[0] = ch, v[1] = ch, len = 1;}
hash(int a, int b, int c) {v[0] = a, v[1] = b, len = c;}
hash operator +(const hash& x) const {
return hash(v[0] * p[0][x.len] + x.v[0], v[1] * p[1][x.len] + x.v[1], len + x.len);
}
ll operator()() const {
return v[0] * mod + v[1];
}
};
hash contr[3][nmax];
void inithash(int _0, int _1) {
p[0][0] = p[0][1] = 1;
p[0][1] = _0;
p[1][1] = _1;
for(int i = 2; i < nmax; i++) {
p[0][i] = p[0][i - 1] * p[0][1] % mod;
p[1][i] = p[1][i - 1] * p[1][1] % mod;
}
contr[0][1] = hash(0);
contr[1][1] = hash(1);
contr[2][1] = hash(2);
for(int i = 2; i < nmax; i++) {
for(int j = 0; j < 3; j++)
contr[j][i] = contr[j][i - 1] + contr[j][1];
}
}
#undef int
unordered_set<int> freq;
int code(tuple<int,int,int> pp) {
int x, y, z;
tie(x, y, z) = pp;
return x * 3 * 3 + y * 3 + z;
}
void decode(int x, int *to) {
to[0] = (x % 3), x /= 3, to[1] = (x % 3), x /= 3, to[2] = (x % 3);
return;
}
#define stack mata
vector<int> stack;
void insert(int x) { if(!freq.count(x)) freq.insert(x), stack.push_back(x); }
void start() {
insert(9);
insert(3);
insert(1);
while(stack.size()) {
int a[3], b[3];
decode(stack.back(), a);
stack.pop_back();
for(auto x : freq) {
decode(x, b);
insert(code({(-a[0] + -b[0] + 6) % 3, (-a[1] + -b[1] + 6) % 3, (-a[2] + -b[2] + 6) % 3}));
}
}
}
int starter[3][nmax];
int v[nmax];
unordered_set<ll> cine;
int n;
namespace AINT {
hash aint[nmax * 4];
int lazy[nmax * 4];
void apply(int node, int cl, int cr) {
if(lazy[node] == -1)
return;
aint[node] = contr[lazy[node]][cr - cl + 1];
if(cl == cr)
return;
lazy[2 * node] = lazy[node];
lazy[2 * node + 1] = lazy[node];
lazy[node] = -1;
}
void prop(int node, int cl, int cr) {
apply(node, cl, cr);
if(cl == cr)
return;
int mid = cl + cr >> 1;
apply(2 * node, cl, mid);
apply(2 * node + 1, mid + 1, cr);
}
void upd(int val, int l, int r, int node = 1, int cl = 1, int cr = n) {
if(l <= cl && cr <= r) {
lazy[node] = val;
prop(node, cl, cr);
return;
}
prop(node, cl, cr);
if(r < cl || cr < l)
return;
int mid = cl + cr >> 1;
upd(val, l, r, 2 * node, cl, mid);
upd(val, l, r, 2 * node + 1, mid + 1, cr);
aint[node] = aint[2 * node] + aint[2 * node + 1];
}
hash constr(int node = 1, int cl = 1, int cr = n) {
lazy[node] = -1;
if(cl == cr)
return (aint[node] = v[cl]);
int mid = cl + cr >> 1;
return aint[node] = constr(node * 2, cl, mid) + constr(2 * node + 1, mid + 1, cr);
}
bool query() {
//cerr << aint[1]() << '\n';
return cine.count(aint[1]());
}
};
int encr[256];
int main() {
encr['O'] = 0;
encr['J'] = 1;
encr['I'] = 2;
char ch;
inithash(29, 101);
start();
cin >> n;
for(int t = 0; t < 3; t++) {
for(int i = 1; i <= n; i++) {
cin >> ch;
starter[t][i] = encr[ch];
}
}
for(auto x : freq) {
int aggr[3];
aggr[0] = x % 3;
x /= 3;
aggr[1] = x % 3;
x /= 3;
aggr[2] = x % 3;
hash rez;
for(int i = 1; i <= n; i++) {
int y = 0;
for(int t = 0; t < 3; t++)
y += aggr[t] * starter[t][i];
y = (y % 3 + 3) % 3;
rez = rez + hash(y);
}
cine.insert(rez());
}
int q;
cin >> q;
for(int i = 1; i <= n; i++)
cin >> ch, v[i] = encr[ch];
AINT::constr();
cout << (AINT::query()? "Yes\n" : "No\n");
for(int i = 0, l, r; i < q; i++) {
cin >> l >> r >> ch;
AINT::upd(encr[ch], l, r);
cout << (AINT::query()? "Yes\n" : "No\n");
}
}
Compilation message
Main.cpp: In function 'void AINT::prop(int, int, int)':
Main.cpp:92:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
92 | int mid = cl + cr >> 1;
| ~~~^~~~
Main.cpp: In function 'void AINT::upd(int, int, int, int, int, int)':
Main.cpp:105:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
105 | int mid = cl + cr >> 1;
| ~~~^~~~
Main.cpp: In function 'uhasfsfjha AINT::constr(int, int, int)':
Main.cpp:114:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
114 | int mid = cl + cr >> 1;
| ~~~^~~~
Main.cpp: In function 'int main()':
Main.cpp:136:28: warning: array subscript has type 'char' [-Wchar-subscripts]
136 | starter[t][i] = encr[ch];
| ^~
Main.cpp:159:28: warning: array subscript has type 'char' [-Wchar-subscripts]
159 | cin >> ch, v[i] = encr[ch];
| ^~
Main.cpp:164:20: warning: array subscript has type 'char' [-Wchar-subscripts]
164 | AINT::upd(encr[ch], l, r);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
397 ms |
36888 KB |
Output is correct |
| 2 |
Correct |
404 ms |
36924 KB |
Output is correct |
| 3 |
Correct |
438 ms |
37020 KB |
Output is correct |
| 4 |
Incorrect |
395 ms |
36804 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
397 ms |
36888 KB |
Output is correct |
| 2 |
Correct |
404 ms |
36924 KB |
Output is correct |
| 3 |
Correct |
438 ms |
37020 KB |
Output is correct |
| 4 |
Incorrect |
395 ms |
36804 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
397 ms |
36888 KB |
Output is correct |
| 2 |
Correct |
404 ms |
36924 KB |
Output is correct |
| 3 |
Correct |
438 ms |
37020 KB |
Output is correct |
| 4 |
Incorrect |
395 ms |
36804 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
397 ms |
36888 KB |
Output is correct |
| 2 |
Correct |
404 ms |
36924 KB |
Output is correct |
| 3 |
Correct |
438 ms |
37020 KB |
Output is correct |
| 4 |
Incorrect |
395 ms |
36804 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
