#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=2e5+5, mod=1e9+7;
ll n, mp[100], q, k[10], l, r;
char ch;
vector<ll> qs[3], d[10], p(nx);
string s[3], t;
struct segtree
{
int d[4*nx], lz[4*nx];
void build(int l, int r, int i)
{
lz[i]=-1;
if (l==r) return void(d[i]=(mp[t[l-1]]*p[l])%mod);
int md=(l+r)/2;
build(l, md, 2*i);
build(md+1, r, 2*i+1);
d[i]=(d[2*i]+d[2*i+1])%mod;
}
void pushlz(int l, int r, int i)
{
if (lz[i]==-1) return;
if (l==r) return d[i]=(p[l]*lz[i])%mod, lz[i]=-1, void();
d[i]=((qs[lz[i]][r]-qs[lz[i]][l-1])%mod+mod)%mod;
lz[2*i]=lz[2*i+1]=lz[i];
lz[i]=-1;
}
void update(int l, int r, int i, int ql, int qr, int vl)
{
pushlz(l, r, i);
if (qr<l||r<ql) return;
if (ql<=l&&r<=qr) return lz[i]=vl, pushlz(l, r, i), void();
int md=(l+r)/2;
update(l, md, 2*i, ql, qr, vl);
update(md+1, r, 2*i+1, ql, qr, vl);
d[i]=(d[2*i]+d[2*i+1])%mod;
}
bool check()
{
pushlz(1, n, 1);
for (int i=0; i<9; i++) if (k[i]==d[1]) return 1;
return 0;
}
} st;
ll getval(vector<ll> &str)
{
ll res=0;
for (int i=1; i<=n; i++) res+=(p[i]*str[i])%mod;
return res;
}
vector<ll> cross(vector<ll> &lhs, vector<ll> &rhs)
{
vector<ll> res(nx);
for (int i=1; i<=n; i++) res[i]=(-lhs[i]-rhs[i]+9)%3;
return res;
}
void show(vector<ll> &x)
{
for (int i=1; i<=n; i++) cout<<x[i];
cout<<'\n';
}
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
for (int i=0; i<3; i++) qs[i].resize(nx), d[i].resize(nx);
mp['J']=0; mp['O']=1; mp['I']=2;
p[1]=1;
for (int i=2; i<nx; i++) p[i]=(p[i-1]*3)%mod;
for (int i=0; i<3; i++) for (int j=1; j<nx; j++) qs[i][j]=(qs[i][j-1]+i*p[j])%mod;
cin>>n>>s[0]>>s[1]>>s[2];
for (int i=0; i<3; i++) for (int j=1; j<=n; j++) d[i][j]=mp[s[i][j-1]];
d[3]=cross(d[0], d[1]);
d[4]=cross(d[0], d[2]);
d[5]=cross(d[1], d[2]);
d[6]=cross(d[3], d[2]);
d[7]=cross(d[4], d[1]);
d[8]=cross(d[5], d[0]);
for (int i=0; i<9; i++) k[i]=getval(d[i]);
//for (int i=3; i<9; i++) show(d[i]);
cin>>q>>t;
st.build(1, n, 1);
cout<<(st.check()?"Yes":"No")<<'\n';
while (q--)
{
cin>>l>>r>>ch;
st.update(1, n, 1, l, r, mp[ch]);
cout<<(st.check()?"Yes":"No")<<'\n';
}
}
Compilation message
Main.cpp: In member function 'void segtree::build(int, int, int)':
Main.cpp:19:46: warning: array subscript has type 'char' [-Wchar-subscripts]
19 | if (l==r) return void(d[i]=(mp[t[l-1]]*p[l])%mod);
| ^
Main.cpp: In function 'int main()':
Main.cpp:80:74: warning: array subscript has type 'char' [-Wchar-subscripts]
80 | for (int i=0; i<3; i++) for (int j=1; j<=n; j++) d[i][j]=mp[s[i][j-1]];
| ^
Main.cpp:95:37: warning: array subscript has type 'char' [-Wchar-subscripts]
95 | st.update(1, n, 1, l, r, mp[ch]);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
24784 KB |
Output is correct |
| 2 |
Correct |
75 ms |
24916 KB |
Output is correct |
| 3 |
Correct |
74 ms |
24804 KB |
Output is correct |
| 4 |
Incorrect |
65 ms |
24820 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
24784 KB |
Output is correct |
| 2 |
Correct |
75 ms |
24916 KB |
Output is correct |
| 3 |
Correct |
74 ms |
24804 KB |
Output is correct |
| 4 |
Incorrect |
65 ms |
24820 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
24784 KB |
Output is correct |
| 2 |
Correct |
75 ms |
24916 KB |
Output is correct |
| 3 |
Correct |
74 ms |
24804 KB |
Output is correct |
| 4 |
Incorrect |
65 ms |
24820 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
24784 KB |
Output is correct |
| 2 |
Correct |
75 ms |
24916 KB |
Output is correct |
| 3 |
Correct |
74 ms |
24804 KB |
Output is correct |
| 4 |
Incorrect |
65 ms |
24820 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
