Submission #231949

#	Time	Username	Problem	Language	Result	Execution time	Memory
231949		MKopchev	Cake (CEOI14_cake)	C++14	83.33 / 100	2091 ms	24184 KiB

cake

#include<bits/stdc++.h>
using namespace std;
const int nmax=2.5e5+42;

int n,a;

int inp[nmax],where[nmax];

int tree[4*nmax];

void update(int node,int l,int r,int pos,int val)
{
    if(l==r)
    {
        tree[node]=val;
        return;
    }
    int av=(l+r)/2;

    if(pos<=av)update(node*2,l,av,pos,val);
    else update(node*2+1,av+1,r,pos,val);

    tree[node]=max(tree[node*2],tree[node*2+1]);
}
int query(int node,int l,int r,int lq,int rq)
{
    if(l==lq&&r==rq)return tree[node];
    int av=(l+r)/2,ret=0;

    if(lq<=av)ret=max(ret,query(node*2,l,av,lq,min(av,rq)));
    if(av<rq)ret=max(ret,query(node*2+1,av+1,r,max(av+1,lq),rq));

    return ret;
}

int pointer=0;

set< pair<int,int> > active;

void make_best(int pos)
{
    pointer++;

    active.erase({inp[pos],pos});

    inp[pos]=pointer;

    active.insert({inp[pos],pos});

    update(1,1,n,pos,inp[pos]);

    //cout<<"make best ";for(int i=1;i<=n;i++)cout<<inp[i]<<" ";cout<<endl;
}

int go_right(int val)
{
    int ok=a,not_ok=n+1;

    while(not_ok-ok>1)
    {
        int av=(ok+not_ok)/2;
        if(query(1,1,n,a+1,av)<val)ok=av;
        else not_ok=av;
    }
    return ok;
}

int go_left(int val)
{
    int ok=a,not_ok=0;

    while(ok-not_ok>1)
    {
        int av=(ok+not_ok)/2;
        if(query(1,1,n,av,a-1)<val)ok=av;
        else not_ok=av;
    }
    return ok;
}
int main()
{
    scanf("%i%i",&n,&a);

    for(int i=1;i<=n;i++)
    {
        scanf("%i",&inp[i]);
        where[inp[i]]=i;
    }

    for(int i=1;i<=n;i++)make_best(where[i]);

    int q;
    scanf("%i",&q);

    for(int i=1;i<=q;i++)
    {
        char c=getchar();
        while(c!='E'&&c!='F')c=getchar();

        if(c=='F')
        {
            int pos;
            scanf("%i",&pos);

            if(pos==a)
            {
                printf("0\n");
                continue;
            }

            int maxi=0;

            if(pos<a)
            {
                maxi=query(1,1,n,pos,a-1);

                int outp=a-pos;

                if(a!=n)outp+=go_right(maxi)-a;

                printf("%i\n",outp);
            }
            else//pos>a
            {
                maxi=query(1,1,n,a+1,pos);

                int outp=pos-a;

                if(a!=1)outp+=a-go_left(maxi);

                printf("%i\n",outp);
            }
        }
        else
        {
            int pos,val;

            scanf("%i%i",&pos,&val);

            make_best(pos);

            set< pair<int,int> >::iterator it=active.end();
            it--;

            vector<int> noted={};

            while(1)
            {
                if((*it).second==pos){it--;continue;}

                if(val==1)break;

                noted.push_back((*it).second);

                val--;
                it--;
            }

            reverse(noted.begin(),noted.end());
            for(auto w:noted)make_best(w);
        }
    }
    return 0;
}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i",&n,&a);
     ~~~~~^~~~~~~~~~~~~~
cake.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&inp[i]);
         ~~~~~^~~~~~~~~~~~~~
cake.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&q);
     ~~~~~^~~~~~~~~
cake.cpp:103:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%i",&pos);
             ~~~~~^~~~~~~~~~~
cake.cpp:138:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%i%i",&pos,&val);
             ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 33.333333 / 50