#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 (x[y].l==x[y].r)
{
q[i].maz=min(q[i].maz,sk+x[y].rez);
sk+=x[y].sum;
return x[y].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,sk+x[y].rez);
sk+=x[y].sum;
//q[i].maz=min(q[i].maz,sk);
return x[y].l;
}
int main()
{
//freopen("1-elections.in","r",stdin);
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++;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
632 KB |
Output is correct |
| 2 |
Execution timed out |
3062 ms |
632 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
632 KB |
Output is correct |
| 2 |
Execution timed out |
3062 ms |
632 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
632 KB |
Output is correct |
| 2 |
Execution timed out |
3062 ms |
632 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
