#include<bits/stdc++.h>
using namespace std;
struct masivs{int l;int r;int poz;int rez;int maz;};
masivs q[500005];
struct segm{int l;int r;int rez;int sum;};
segm x[2000006];
int i,j,n,m,l,d,r,mas[500005],a[2],rez,maz,sum[500005],sk;
vector<int> k;
vector<int>::iterator it;
vector<int> del;
char c;
bool c1(masivs maz,masivs liel)
{
if (maz.l==liel.l)
{
return maz.r>liel.r;
}
return maz.l>liel.l;
}
bool c2(masivs maz,masivs liel)
{
return maz.poz<liel.poz;
}
int bins(int l,int r,int y)
{
int c=l+(r-l)/2;
//cout << l << " " << c << " " << r << " " << del[c] << " " << y << "\n";
if (l==r)
{
return l;
}
if (del[c]>y)
{
return bins(c+1,r,y);
}
else
{
return bins(l,c,y);
}
}
void build(int y,int l,int r)
{
x[y].l=l;
x[y].r=r;
if (l!=r)
{
build(2*y+1,l,l+(r-l)/2);
build(2*y+2,l+(r-l)/2+1,r);
x[y].sum=x[2*y+1].sum+x[2*y+2].sum;
x[y].rez=min(x[2*y+2].rez,x[2*y+1].rez+x[2*y+2].sum);
//x[y].rez=min(min(x[2*y+1].rez,x[2*y+2].rez),x[y].sum);
}
else
{
x[y].rez=mas[l];
x[y].sum=mas[l];
}
//cout << y << " " << l << " " << r << " " << x[y].rez << "\n";
}
void mod(int y,int g)
{
if (x[y].l!=x[y].r)
{
if (g<x[2*y+2].l)
{
mod(2*y+1,g);
}
else
{
mod(2*y+2,g);
}
x[y].sum=x[2*y+1].sum+x[2*y+2].sum;
x[y].rez=min(x[2*y+2].rez,x[2*y+1].rez+x[2*y+2].sum);
}
else
{
if (x[y].sum==0)
{
x[y].sum=mas[x[y].l];
x[y].rez=mas[x[y].l];
}
else
{
x[y].sum=0;
x[y].rez=0;
}
}
}
int f(int y,int l,int r)
{
//cout << x[y].l << " " << x[y].r << " " << l << " " << r << " " << x[y].rez << "\n";
if (l==r)
{
q[i].maz=min(q[i].maz,x[y].rez);
return l;
}
if (r<=x[2*y+1].r)
{
return f(2*y+1,l,r);
}
if (r!=x[y].r)
{
return f(2*y+2,l,r);
}
if (l>x[y].l)
{
return f(2*y+2,l,r);
}
q[i].maz=min(q[i].maz,x[y].rez);
if (sk>0)
{
sk=0;
}
sk+=x[y].sum;
q[i].maz=min(q[i].maz,sk);
return l;
}
int main()
{
cin.sync_with_stdio(0);
cin.tie(0);
cin >> n;
i=0;
while (i<n)
{
cin >> c;
if (c=='C')
{
mas[i]=1;
}
else
{
mas[i]=-1;
}
i++;
}
i=n-1;
while (i>=0)
{
sum[i]=sum[i+1]+mas[i];
i--;
}
cin >> m;
i=0;
while (i<m)
{
cin >> q[i].l >> q[i].r;
q[i].l--;
q[i].r--;
q[i].poz=i;
i++;
}
sort(q,q+m,c1);
build(0,0,n-1);
j=n-1;
i=0;
while (i<m)
{
while (j>=0&&j>=q[i].l)
{
if (mas[j]==-1)
{
del.push_back(j);
mod(0,j);
}
else if (!del.empty())
{
mod(0,del.back());
del.pop_back();
}
j--;
}
q[i].rez=del.size()-bins(0,del.size()-1,q[i].r);
if (del[-q[i].rez+del.size()]>q[i].r)
{
q[i].rez--;
}
d=q[i].r;
sk=0;
while (d>=q[i].l)
{
d=f(0,q[i].l,d)-1;
}
//cout << q[i].rez << " " << q[i].maz << "\n";
i++;
}
sort(q,q+m,c2);
i=0;
while (i<m)
{
cout << q[i].rez-q[i].maz << "\n";
i++;
}
/*i=0;
while (i<m)
{
cin >> l >> r;
l--;
r--;
j=l;
a[0]=0;
a[1]=0;
k.clear();
rez=0;
maz=1000000000;
while (j<=r)
{
a[max(0,mas[j])]++;
maz=min(maz,sum[j]);
if (a[1]<a[0])
{
a[max(0,mas[j])]--;
k.push_back(j);
maz++;
rez++;
}
j++;
}
rez+=max(0,-maz+sum[r+1]);
cout << rez << "\n";
i++;
}*/
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
