Submission #267046

#	Time	Username	Problem	Language	Result	Execution time	Memory
267046		stefantaga	Election (BOI18_election)	C++14	0 / 100	2 ms	512 KiB

election

#include <bits/stdc++.h>

using namespace std;
int n,i;
struct wow
{
    int pref,sum,suf;
}arb[2000005],arb1[2000005];
char ch;
int minim,suma;
void update (int st,int dr,int nod ,int poz ,int val,wow arb[2000005])
{
    if (st==dr)
    {
        arb[nod].pref=val;
        arb[nod].suf=val;
        arb[nod].sum=val;
        return;
    }
    int mij=(st+dr)/2;
    if (poz<=mij)
    {
        update (st,mij,2*nod,poz,val,arb);
    }
    else
    {
        update(mij+1,dr,2*nod+1,poz,val,arb);
    }
    arb[nod].sum=arb[2*nod].sum+arb[2*nod+1].sum;
    arb[nod].pref=min(arb[2*nod].pref,arb[2*nod].sum+arb[2*nod+1].pref);
    arb[nod].suf=min(arb[2*nod+1].suf,arb[2*nod+1].sum+arb[2*nod].suf);
}
void query (int st,int dr,int nod,int ua ,int ub,wow arb[2000005])
{
    if (ua<=st&&dr<=ub)
    {
        minim=min(minim,suma+arb[nod].pref);
        suma+=arb[nod].sum;
        return ;
    }
    int mij=(st+dr)/2;
    if (ua<=mij)
    {
        query(st,mij,2*nod,ua,ub,arb);
    }
    if (mij<ub)
    {
        query(mij+1,dr,2*nod+1,ua,ub,arb);
    }
}
void querysuf (int st,int dr,int nod,int ua ,int ub,wow arb[2000005])
{
    if (ua<=st&&dr<=ub)
    {
        minim=min(minim,suma+arb[nod].suf);
        suma+=arb[nod].sum;
        return ;
    }
    int mij=(st+dr)/2;
    if (mij<ub)
    {
        querysuf(mij+1,dr,2*nod+1,ua,ub,arb);
    }
    if (ua<=mij)
    {
        querysuf(st,mij,2*nod,ua,ub,arb);
    }
}
int q,x,y,v[500005],solutie;
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>n;
    for (i=1;i<=n;i++)
    {
        cin>>ch;
        if (ch=='C')
        {
            v[i]=1;
            update(1,n,1,i,1,arb);
        }
        else
        {
            v[i]=-1;
            update(1,n,1,i,-1,arb);
        }
    }
    cin>>q;
    for (i=1;i<=q;i++)
    {
        cin>>x>>y;
        solutie=INT_MAX;
        minim=INT_MAX;suma=0;
        query(1,n,1,x,y,arb);
        solutie=min(solutie,minim);
        minim=INT_MAX;suma=0;
        querysuf(1,n,1,x,y,arb);
        solutie=min(solutie,minim);
        cout<<max(0-solutie,0)<<'\n';
    }
    return 0;
}

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