#include <bits/stdc++.h>
using namespace std;
int const MAXN=2e6, K=(1<<2);
int n, q;
string a, b, c, p;
bool tree[2*K-1];
char lazy[2*K-1];
int jprefix[MAXN], oprefix[MAXN], iprefix[MAXN];
bool good(int l, int r, char c)
{
r=min(r, n)-1;
if (l>r)
return true;
int total;
if (c=='J')
{
total=jprefix[r];
if (l!=0)
total=total-jprefix[l-1];
}
if (c=='O')
{
total=oprefix[r];
if (l!=0)
total=total-oprefix[l-1];
}
if (c=='I')
{
total=iprefix[r];
if (l!=0)
total=total-iprefix[l-1];
}
return total==r-l+1;
}
void propagate(int x, int l, int r)
{
if (lazy[x]=='#')
return;
if (r-l==1)
{
lazy[x]='#';
return;
}
tree[2*x+1]=good(l, (l+r)/2, lazy[x]);
lazy[2*x+1]=lazy[x];
tree[2*x+2]=good((l+r)/2, r, lazy[x]);
lazy[2*x+2]=lazy[x];
lazy[x]='#';
return;
}
void update(int x, int l, int r, char c, int lt, int rt)
{
if (l>=rt || r<=lt)
return;
if (l>=lt && r<=rt)
{
tree[x]=good(l, r, c);
lazy[x]=c;
return;
}
propagate(x, l, r);
update(2*x+1, l, (l+r)/2, c, lt, rt);
update(2*x+2, (l+r)/2, r, c, lt, rt);
if (r-l==1)
{
if (l>=n)
tree[x]=true;
else
tree[x]=(a[l]==c);
}
else
tree[x]=(tree[2*x+1]&tree[2*x+2]);
//cout << "l r c " << l << " " << r << " " << c << " " << tree[x] << '\n';
return;
}
int main()
{
cin >> n >> a >> b >> c;
cin >> q >> p;
for (int i=0; i<2*K-1; i++)
{
tree[i]=true;
lazy[i]='#';
}
jprefix[0]=0;
oprefix[0]=0;
iprefix[0]=0;
if (a[0]=='J')
jprefix[0]=1;
if (a[0]=='O')
oprefix[0]=1;
if (a[0]=='I')
iprefix[0]=1;
for (int i=1; i<n; i++)
{
jprefix[i]=jprefix[i-1];
oprefix[i]=oprefix[i-1];
iprefix[i]=iprefix[i-1];
if (a[i]=='J')
jprefix[i]=jprefix[i]+1;
if (a[i]=='O')
oprefix[i]=oprefix[i]+1;
if (a[i]=='I')
iprefix[i]=iprefix[i]+1;
}
for (int i=0; i<n; i++)
update(0, 0, K, p[i], i, i+1);
//cout << "treee" << '\n';
//for (int i=0; i<2*K-1; i++)
// cout << tree[i] << " ";
//cout << '\n';
if (tree[0])
cout << "Yes" << '\n';
else
cout << "No" << '\n';
while (q--)
{
int l, r;
char c;
cin >> l >> r >> c;
l=l-1;
update(0, 0, K, c, l, r);
if (tree[0])
cout << "Yes" << '\n';
else
cout << "No" << '\n';
}
return 0;
}
Compilation message
Main.cpp: In function 'bool good(int, int, char)':
Main.cpp:37:23: warning: 'total' may be used uninitialized in this function [-Wmaybe-uninitialized]
37 | return total==r-l+1;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
287 ms |
5068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
287 ms |
5068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
287 ms |
5068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
287 ms |
5068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
