#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll MOD = 1000000007;
vector<int> nums[3];
vector<int> anss[9];
vector<int> tar;
vector<pair<pair<int, int>, int>> qs;
bool good[300001];
ll pow3[300001][4], sum3[300001][4];
ll ha[9][4];
vector<ll> ps = {1000000007, 1000000009, 1000000021, 1000000033};
vector<int> combine(vector<int> v1, vector<int> v2) {
vector<int> v;
v.resize(v1.size());
for(int i = 0; i < v.size(); i++) v[i] = (6 - v1[i] - v2[i])%3;
return v;
}
struct segTree {
ll prime; int typ;
vector<ll> nums, ops;
int size = 1;
void init(int n, ll p, int t) {
while(size < n) size *= 2;
vector<ll>().swap(nums);
nums.resize(2*size, 0);
ops.resize(2*size, -1);
prime = p;
typ = t;
}
void prop(int n, int d) {
if(ops[n] == -1) return;
if(n >= size) {
nums[n] = ops[n];
ops[n] = -1;
return;
}
prop(2*n+1, d);
prop(2*n+2, d);
ops[2*n+1] = ops[n];
ops[2*n+2] = ops[n];
nums[n] = (ops[n] * sum3[d-1][typ])%prime;
ops[n] = -1;
return;
}
void set(int l, int r, int v, int n, int lx, int rx) {
prop(n, rx - lx);
if(l >= rx || lx >= r) return;
if(l <= lx && rx <= r) {
ops[n] = v;
nums[n] = (ops[n] * sum3[rx-lx-1][typ])%prime;
return;
}
int mid = (lx + rx)/2;
set(l, r, v, 2*n+1, lx, mid);
set(l, r, v, 2*n+2, mid, rx);
nums[n] = (pow3[mid - lx][typ] * nums[2*n+1] + nums[2*n+2])%prime;
return;
}
void set(int l, int r, int v) {
set(l, r, v, 0, 0, size);
}
ll get() {
prop(0, size);
return nums[0];
}
};
segTree st[4];
int getChar(char c) {
if(c == 'J') return 0;
if(c == 'O') return 1;
return 2;
}
bool check() {
for(int i = 0; i < 9; i++) {
bool sad = false;
for(int z = 0; z < 3; z++) {
if(st[z].get() != ha[i][z]) sad = true;
// cout << st[z].get() << ' ';
}
// cout << '\n';
if(!sad) return true;
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll k = 1;
for(int z = 0; z < 3; z++) {
k = 1;
for(int i = 0; i <= 300000; i++) {
pow3[i][z] = k;
k *= 3;
if(k > ps[z]) k %= ps[z];
if(i == 0) sum3[i][z] = pow3[i][z];
else sum3[i][z] = (sum3[i-1][z] + pow3[i][z])%ps[z];
}
}
int n, q;
int size = 1;
string s;
cin >> n;
while(size < n) {
size *= 2;
}
for(int i = 0; i < 3; i++) {
cin >> s;
nums[i].resize(n);
for(int j = 0; j < n; j++) {
if(s.at(j) == 'J') nums[i][j] = 0;
else if(s.at(j) == 'O') nums[i][j] = 1;
else nums[i][j] = 2;
}
anss[i] = nums[i];
}
anss[3] = combine(nums[0], nums[1]);
anss[4] = combine(nums[1], nums[2]);
anss[5] = combine(nums[0], nums[2]);
anss[6] = combine(anss[3], nums[2]);
anss[7] = combine(anss[4], nums[0]);
anss[8] = combine(anss[5], nums[1]);
for(int z = 0; z < 3; z++) {
for(int i = 0; i < 9; i++) {
ll k = 0;
for(int j = 0; j < size; j++) {
k *= 3;
if(j < anss[i].size()) k += anss[i][j];
k %= ps[z];
}
ha[i][z] = k;
// cout << ha[i][z] << ' ';
}
// cout << '\n';
}
cin >> q >> s;
tar.resize(n);
qs.resize(q);
for(int z = 0; z < 2; z++) {
st[z].init(n, ps[z], z);
}
for(int z = 0; z < 2; z++) {
for(int i = 0; i < n; i++) {
st[z].set(i, i+1, getChar(s.at(i)));
}
}
good[0] = check();
for(int i = 0; i < q; i++) {
int x, y;
char c;
cin >> x >> y >> c;
int z;
if(c == 'J') z = 0;
else if(c == 'O') z = 1;
else z = 2;
for(int m = 0; m < 3; m++) st[m].set(x-1, y, z);
good[i+1] = check();
}
for(int i = 0; i <= q; i++) {
if(good[i]) cout << "Yes\n";
else cout << "No\n";
}
}
Compilation message
Main.cpp: In function 'std::vector<int> combine(std::vector<int>, std::vector<int>)':
Main.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(int i = 0; i < v.size(); i++) v[i] = (6 - v1[i] - v2[i])%3;
| ~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:137:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | if(j < anss[i].size()) k += anss[i][j];
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
44 ms |
42900 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
44 ms |
42900 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
44 ms |
42900 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
44 ms |
42900 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
