#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define endl '\n'
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
const int mod = 1e9 + 13, base = 5;
const int N = 1e6 + 15;
const ll inf = 1e18;
vector<int> s[3];
int T[N];
char str[N];
int n, Q;
struct Sgt{
#define ls (idx<<1)
#define rs (idx<<1|1)
static const int off = (1<<18);
struct data{
int pws, val, tag;
} t[N<<2];
void pull(int idx){
t[idx].pws = t[ls].pws + t[rs].pws;
t[idx].val = t[ls].val + t[rs].val;
return;
}
void push(int idx){
if (~t[idx].tag){
t[idx].val = t[idx].pws * t[idx].tag % mod;
if (idx < off) t[ls].tag = t[rs].tag = t[idx].tag;
t[idx].tag = ~0;
}
return;
}
void build(){
for (int idx=off, p=1;idx<off*2;idx++, p=1ll*p*base%mod){
t[idx].pws = p;
t[idx].val = p*T[idx-off];
t[idx].tag = ~0;
}
for (int idx=off-1;idx>=1;idx--){
t[idx].pws = t[ls].pws+t[rs].pws;
t[idx].val = t[ls].val+t[rs].val;
t[idx].tag = ~0;
}
}
void update(int l, int r, int val, int idx=1, int lo=0, int hi=off){
push(idx);
if (r<=lo||hi<=l) return;
if (l<=lo&&hi<=r){
t[idx].tag = val;
push(idx);
return;
}
int mi = (lo+hi) >> 1;
update(l, r, val, ls, lo, mi);
update(l, r, val, rs, mi, hi);
pull(idx);
}
#undef ls
#undef rs
} seg;
int hsh(vector<int> cur){
int res = 0;
for (int i=0, p=1;i<n;i++, p=1ll*p*base % mod){
res = (res + 1ll*cur[i]*p) % mod;
}
return res;
}
vector<int> cross(vector<int> lhs, vector<int> rhs){
vector<int> cur(n);
for (int i=0, p=1;i<n;i++, p = 1ll*p*base%mod){
int c;
if (lhs[i]==rhs[i]) c = lhs[i];
else if (lhs[i]!=0&&rhs[i]!=0) c = 0;
else if (lhs[i]!=1&&rhs[i]!=1) c = 1;
else if (lhs[i]!=2&&rhs[i]!=2) c = 2;
cur[i] = c;
}
return cur;
}
int main(){
cin >> n;
for (int k=0;k<3;k++){
scanf("%s", str);
s[k].resize(n);
for (int i=0;i<n;i++){
if (str[i]=='J') s[k][i] = 0;
if (str[i]=='O') s[k][i] = 1;
if (str[i]=='I') s[k][i] = 2;
}
}
set<int> st;
st.insert(hsh(s[0]));
st.insert(hsh(s[1]));
st.insert(hsh(s[2]));
st.insert(hsh(cross(s[0],s[1])));
st.insert(hsh(cross(s[1],s[2])));
st.insert(hsh(cross(s[0],s[2])));
st.insert(hsh(cross(s[0],cross(s[1],s[2]))));
st.insert(hsh(cross(s[1],cross(s[0],s[2]))));
st.insert(hsh(cross(s[2],cross(s[0],s[1]))));
scanf("%d", &Q);
scanf("%s", str);
for (int i=0;i<n;i++){
if (str[i]=='J') T[i] = 0;
if (str[i]=='O') T[i] = 1;
if (str[i]=='I') T[i] = 2;
}
seg.build();
if (st.find(seg.t[1].val)!=st.end()){
puts("Yes");
}
else {
puts("No");
}
while (Q--){
int L, R;
char C;
scanf("%d %d %c", &L, &R, &C);
int c=0;
if (C=='J') c = 0;
if (C=='O') c = 1;
if (C=='I') c = 2;
seg.update(L-1, R, c);
int val = seg.t[1].val;
if (st.find(val)!=st.end()){
puts("Yes");
}
else {
puts("No");
}
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | scanf("%s", str);
| ~~~~~^~~~~~~~~~~
Main.cpp:106:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
106 | scanf("%d", &Q);
| ~~~~~^~~~~~~~~~
Main.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
107 | scanf("%s", str);
| ~~~~~^~~~~~~~~~~
Main.cpp:123:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
123 | scanf("%d %d %c", &L, &R, &C);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'std::vector<int> cross(std::vector<int>, std::vector<int>)':
Main.cpp:81:10: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
81 | cur[i] = c;
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
87 ms |
11348 KB |
Output is correct |
| 2 |
Correct |
95 ms |
11448 KB |
Output is correct |
| 3 |
Correct |
91 ms |
11344 KB |
Output is correct |
| 4 |
Incorrect |
86 ms |
11232 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
87 ms |
11348 KB |
Output is correct |
| 2 |
Correct |
95 ms |
11448 KB |
Output is correct |
| 3 |
Correct |
91 ms |
11344 KB |
Output is correct |
| 4 |
Incorrect |
86 ms |
11232 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
87 ms |
11348 KB |
Output is correct |
| 2 |
Correct |
95 ms |
11448 KB |
Output is correct |
| 3 |
Correct |
91 ms |
11344 KB |
Output is correct |
| 4 |
Incorrect |
86 ms |
11232 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
87 ms |
11348 KB |
Output is correct |
| 2 |
Correct |
95 ms |
11448 KB |
Output is correct |
| 3 |
Correct |
91 ms |
11344 KB |
Output is correct |
| 4 |
Incorrect |
86 ms |
11232 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
