Submission #68587

#	Time	Username	Problem	Language	Result	Execution time	Memory
68587		renatsj	Election (BOI18_election)	C++14	0 / 100	4 ms	504 KiB

election

#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;
}

• Subtask 1: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18