#include<bits/stdc++.h>
using namespace std;
#define int long long
#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 + 7;
const int N = 1e6 + 15;
const ll inf = 1e18;
template<class T> bool ckmin(T &a, T b){
return (a > b ? a=b, true : false);
}
template<class T> bool ckmax(T &a, T b){
return (a < b ? a=b, true : false);
}
int mul(int a, int b){
return (a*b)%mod;
}
int add(int a, int b){
int c = (a+b)%mod;
if (c<0) c += mod;
return c;
}
int sub(int a, int b){
return add(a, -b);
}
int pw(int a, int b){
int r = 1;
while (b){
if (b&1){
r=mul(a,r);
}
a = mul(a, a);
b >>= 1;
}
return r;
}// !!
int inv(int a){
return pw(a, mod-2);
}
#define ls (idx << 1)
#define rs (idx << 1 | 1)
const int off = (1<<3);
int t[off*2];
int lazy[off*2];
int A[N];
int n;
void push(int idx, int lo, int hi){
if (!lazy[idx]) return;
int val = lazy[idx];
t[idx] = mul(add(pw(3ll, hi),1ll), inv(sub(3, 1)));
t[idx] = sub(t[idx], mul(add(pw(3ll, lo),1ll), inv(sub(3, 1))));
t[idx] = mul(t[idx], val);
if (idx < off) {
lazy[ls] = lazy[idx];
lazy[rs] = lazy[idx];
}
lazy[idx] = 0;
}
void update(int l, int r, int val, int idx=1, int lo=0, int hi=off){
push(idx,lo,hi);
if (lo>=r||hi<=l) return;
if (lo>=l&&hi<=r) {
lazy[idx]=val;
push(idx, lo, hi);
return;
}
int mi = (lo+hi)/2;
update(l,r,val,ls,lo,mi);
update(l,r,val,rs,mi,hi); t[idx] = (t[ls]+t[rs])%mod;
}
void build(int idx){
if (idx>=off){
t[idx] = mul(A[idx-off],pw(3ll, idx-off));
return;
}
build(ls);build(rs);
t[idx] = (t[ls]+t[rs])%mod;
return;
}
int hsh(string s){
int p = 1;
int r = 0;
for (int i=0;i<n;i++){
if (s[i]=='J') r = add(r, p*0);
if (s[i]=='O') r = add(r, p*1);
if (s[i]=='I') r = add(r, p*2);
p = mul(p, 3ll);
}
return r;
}
string cross(string a, string b){
string tm;
tm.resize(n);
for (int i=0;i<n;i++){
if (a[i]==b[i]) tm[i] = a[i];
else {
if ('J'!=a[i]&&'J'!=b[i]) tm[i] = 'J';
else if ('O'!=a[i]&&'O'!=b[i]) tm[i] = 'O';
else if ('I'!=a[i]&&'I'!=b[i]) tm[i] = 'I';
}
}
return tm;
}
int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin >> n;
string a,b,c;
cin >> a >> b >> c;
set<int> st;
st.insert(hsh(a));
st.insert(hsh(b));
st.insert(hsh(c));
st.insert(hsh(cross(a,b)));
st.insert(hsh(cross(a,c)));
st.insert(hsh(cross(b,c)));
st.insert(hsh(cross(a,cross(b,c))));
int q;
cin >> q;
string tm;
cin >> tm;
for (int i=0;i<n;i++){
if (tm[i]=='J')A[i]=0;
if (tm[i]=='O')A[i]=1;
if (tm[i]=='I')A[i]=2;
}
build(1);
if (st.find(t[1])!=st.end()){
cout << "Yes\n";
}
else {
cout << "No\n";
}
while (q--){
int l, r;
char x;
cin >> l >> r >> x;
if (x=='J'){
update(l-1, r, 0);
}
if (x=='O'){
update(l-1, r, 1);
}
if (x=='I'){
update(l-1, r, 2);
}
if (st.find(t[1])!=st.end()){
cout << "Yes\n";
}
else {
cout << "No\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
2428 KB |
Output is correct |
| 2 |
Correct |
36 ms |
2384 KB |
Output is correct |
| 3 |
Correct |
85 ms |
2288 KB |
Output is correct |
| 4 |
Incorrect |
37 ms |
2384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
2428 KB |
Output is correct |
| 2 |
Correct |
36 ms |
2384 KB |
Output is correct |
| 3 |
Correct |
85 ms |
2288 KB |
Output is correct |
| 4 |
Incorrect |
37 ms |
2384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
2428 KB |
Output is correct |
| 2 |
Correct |
36 ms |
2384 KB |
Output is correct |
| 3 |
Correct |
85 ms |
2288 KB |
Output is correct |
| 4 |
Incorrect |
37 ms |
2384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
2428 KB |
Output is correct |
| 2 |
Correct |
36 ms |
2384 KB |
Output is correct |
| 3 |
Correct |
85 ms |
2288 KB |
Output is correct |
| 4 |
Incorrect |
37 ms |
2384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
