Submission #231951

#	Time	Username	Problem	Language	Result	Execution time	Memory
231951		MKopchev	Cake (CEOI14_cake)	C++14	100 / 100	1725 ms	18676 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 cur_node,cur_l,cur_r;

void go_down(int node,int l,int r,int lq,int rq,int val)
{
    if(cur_node!=-1)return;

    if(l==lq&&r==rq)
    {
        if(tree[node]>val)
        {
            cur_node=node;
            cur_l=l;
            cur_r=r;
        }
        return;
    }

    int av=(l+r)/2;

    if(av+1<=rq)go_down(node*2+1,av+1,r,max(av+1,lq),rq,val);
    if(lq<=av)go_down(node*2,l,av,lq,min(av,rq),val);
}
int go_left(int val)
{
    cur_node=-1;
    cur_l=-1;
    cur_r=-1;

    go_down(1,1,n,1,a-1,val);

    if(cur_node==-1)return 0;

    while(cur_l!=cur_r)
    {
        int av=(cur_l+cur_r)/2;

        if(tree[cur_node*2+1]>val)cur_node=cur_node*2+1,cur_l=av+1;
        else cur_node=cur_node*2,cur_r=av;
    }
    return cur_l;
}
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-1-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:112: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:116:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&inp[i]);
         ~~~~~^~~~~~~~~~~~~~
cake.cpp:123:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&q);
     ~~~~~^~~~~~~~~
cake.cpp:133:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%i",&pos);
             ~~~~~^~~~~~~~~~~
cake.cpp:168: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: 50 / 50