#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 2e5 + 10;
int MOD;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
if(p==0) return 1 % MOD;
int r = bm(b, p >> 1);
if(p&1) return (((r*r) % MOD) * b) % MOD;
return (r*r) % MOD;
}
int inv(int b) {
return bm(b, MOD-2);
}
int fastlog(int x) {
return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
string gene(string a, string b) {
string c;
for(int i=0; i<a.size(); i++) {
if(a[i] == b[i]) c += a[i];
else {
string t = "JOI";
for(int j=0; j<3; j++) {
if(a[i] != t[j] && b[i] != t[j]) c += t[j];
}
}
}
return c;
}
int random_prime(int l, int r) {
while(1) {
int x = rnd(l, r);
int c = 0;
for(int i=1; i*i<=x; i++) {
if(x%i == 0) {
c+=2;
if(i*i == x) c--;
}
}
if(c==2) return x;
}
return 1226;
}
int geometric_sequence_sum(int a, int x, int n) {
// S = ax^0+ax^1+...+ax^(n-1)
// xS = ax^1+ax^2+...+ax^n
// (x-1)S = ax^n-a
// S = a(x^n-1)/(x-1)
int s = a;
s *= bm(x, n) - 1;
s %= MOD;
s *= inv(x - 1);
s %= MOD;
return s;
}
int pre[MAXN];
int ans, n;
void add_segment(int l, int r, int v) {
ans += geometric_sequence_sum(bm(3, n-r-1), 3, r-l+1) * v;
ans %= MOD;
}
void sub_segment(int l, int r, int v) {
ans -= geometric_sequence_sum(bm(3, n-r-1), 3, r-l+1) * v;
ans += (MOD << 1);
ans %= MOD;
}
void solve(int tc) {
MOD = random_prime(5e8, 1.25 * 1e9);
cin >> n;
pre[0] = 1;
for(int i=1; i<=n; i++) {
pre[i] = (pre[i-1] * 3) % MOD;
}
string s[9];
cin >> s[0] >> s[1] >> s[2];
s[3] = gene(s[0], s[1]);
s[4] = gene(s[0], s[2]);
s[5] = gene(s[1], s[2]);
s[6] = gene(s[2], s[3]);
s[7] = gene(s[1], s[4]);
s[8] = gene(s[0], s[5]);
int h[9];
for(int i=0; i<9; i++) {
h[i] = 0;
for(int j=0; j<n; j++) {
h[i] = (h[i] * 3 + (s[i][j] == 'J' ? 0 : (s[i][j] == 'O' ? 1 : 2))) % MOD;
}
}
int q;
cin >> q;
string def;
cin >> def;
for(char c: def) ans = (ans * 3 + (c == 'J' ? 0 : (c == 'O' ? 1 : 2))) % MOD;
bool yes = 0;
for(int i=0; i<9; i++) yes |= (ans == h[i]);
cout << (yes ? "Yes\n" : "No\n");
set<pair<pair<int,int>,int> > ranges;
for(int i=0; i<def.size(); i++) {
int j = i;
while(j+1 < def.size() && def[j+1] == def[i]) j++;
ranges.insert({{i, j}, (def[i] == 'J' ? 0 : (def[i] == 'O' ? 1 : 2))});
}
for(int i=0; i<q; i++) {
int l, r;
cin >> l >> r;
--l, --r;
char c;
cin >> c;
auto it = ranges.lower_bound({{l, 0}, 0});
if(it != ranges.begin()) it--;
vector<pair<pair<int,int>,int> > to_add, to_sub;
to_add.push_back({{l, r}, (c == 'J' ? 0 : (c == 'O' ? 1 : 2))});
while(it != ranges.end() && (*it).first.first <= r) {
if((*it).first.second >= l) { // relevant
to_sub.push_back(*it);
if((*it).first.first < l) {
to_add.push_back({{(*it).first.first, l-1}, (*it).second});
}
if((*it).first.second > r) {
to_add.push_back({{r+1, (*it).first.second}, (*it).second});
}
}
it++;
}
for(auto x: to_sub) {
ranges.erase(x);
sub_segment(x.first.first, x.first.second, x.second);
}
for(auto x: to_add) {
ranges.insert(x);
add_segment(x.first.first, x.first.second, x.second);
}
bool yes = 0;
for(int i=0; i<9; i++) {
if(h[i] == ans) yes = 1;
}
cout << (yes ? "Yes\n" : "No\n");
}
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1; //cin >> t;
for(int i=1; i<=t; i++) solve(i);
}
Compilation message
Main.cpp: In function 'std::string gene(std::string, std::string)':
Main.cpp:25:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for(int i=0; i<a.size(); i++) {
| ~^~~~~~~~~
Main.cpp: In function 'void solve(long long int)':
Main.cpp:105:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for(int i=0; i<def.size(); i++) {
| ~^~~~~~~~~~~
Main.cpp:107:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | while(j+1 < def.size() && def[j+1] == def[i]) j++;
| ~~~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
554 ms |
2276 KB |
Output is correct |
| 2 |
Correct |
635 ms |
2416 KB |
Output is correct |
| 3 |
Correct |
512 ms |
2244 KB |
Output is correct |
| 4 |
Incorrect |
515 ms |
2400 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
554 ms |
2276 KB |
Output is correct |
| 2 |
Correct |
635 ms |
2416 KB |
Output is correct |
| 3 |
Correct |
512 ms |
2244 KB |
Output is correct |
| 4 |
Incorrect |
515 ms |
2400 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
554 ms |
2276 KB |
Output is correct |
| 2 |
Correct |
635 ms |
2416 KB |
Output is correct |
| 3 |
Correct |
512 ms |
2244 KB |
Output is correct |
| 4 |
Incorrect |
515 ms |
2400 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
554 ms |
2276 KB |
Output is correct |
| 2 |
Correct |
635 ms |
2416 KB |
Output is correct |
| 3 |
Correct |
512 ms |
2244 KB |
Output is correct |
| 4 |
Incorrect |
515 ms |
2400 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
