Submission #223614

#	Time	Username	Problem	Language	Result	Execution time	Memory
223614		Andrei_Cotor	Election (BOI18_election)	C++11	100 / 100	657 ms	44408 KiB

election

#include<fstream>
#include<vector>
#include<deque>
#include<algorithm>
#include<iostream>

using namespace std;

//ifstream fi("election.in");
//ofstream fo("election.out");

char S[500005];
vector<pair<int,int> > Q[500005];
deque<int> Canceled;
int Rez[500005];
int MinSuf[2000005],Sum[2000005];

void update(int nod, int st, int dr, int poz, int val)
{
    if(st==dr)
    {
        MinSuf[nod]=min(0,val);
        Sum[nod]=val;
        return;
    }

    int mij=(st+dr)/2;

    if(poz<=mij)
        update(2*nod,st,mij,poz,val);
    else
        update(2*nod+1,mij+1,dr,poz,val);

    Sum[nod]=Sum[2*nod]+Sum[2*nod+1];
    MinSuf[nod]=min(MinSuf[2*nod+1],Sum[2*nod+1]+MinSuf[2*nod]);
}

int sumsuf;

int getDecalaj(int nod, int st, int dr, int l, int r)
{
    if(l<=st && dr<=r)
    {
        int _sumsuf=sumsuf;
        sumsuf+=Sum[nod];
        return _sumsuf+MinSuf[nod];
    }

    int mij=(st+dr)/2;
    int rez=0;

    if(r>mij)
        rez=min(rez,getDecalaj(2*nod+1,mij+1,dr,l,r));
    if(l<=mij)
        rez=min(rez,getDecalaj(2*nod,st,mij,l,r));

    return rez;
}

int src(int poz)
{
    int rez=-1;
    for(int i=18; i>=0; i--)
    {
        if(rez+(1<<i)<Canceled.size() && Canceled[rez+(1<<i)]>poz)
            rez+=(1<<i);
    }

    return Canceled.size()-rez-1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin>>n;
    cin>>(S+1);

    int q;
    cin>>q;
    for(int i=1; i<=q; i++)
    {
        int x,y;
        cin>>x>>y;

        Q[x].push_back({y,i});
    }

    for(int i=n; i>=1; i--)
    {
        if(S[i]=='C')
        {
            update(1,1,n,i,1);
            if(!Canceled.empty())
            {
                int last=Canceled.back();
                Canceled.pop_back();

                update(1,1,n,last,-1);
            }
        }
        else
        {
            Canceled.push_back(i);
        }

        for(auto qry:Q[i])
        {
            int dr=qry.first;
            int ind=qry.second;

            sumsuf=0;
            int stdr=src(dr);
            int drst=-getDecalaj(1,1,n,i,dr);
            Rez[ind]=stdr+drst;
        }
    }

    for(int i=1; i<=q; i++)
        cout<<Rez[i]<<"\n";
    //fi.close();
    //fo.close();
    return 0;
}

Compilation message (stderr)

election.cpp: In function 'int src(int)':
election.cpp:65:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(rez+(1<<i)<Canceled.size() && Canceled[rez+(1<<i)]>poz)
            ~~~~~~~~~~^~~~~~~~~~~~~~~~

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