oj.uz

Submission #231951

# Submission time Handle Problem Language Result Execution time Memory
231951 2020-05-15T13:18:15 Z MKopchev Cake (CEOI14_cake) C++14
100 / 100
 1725 ms 18676 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 12 ms 384 KB Output is correct
5 Correct 30 ms 1236 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 690 ms 1504 KB Output is correct
2 Correct 371 ms 1532 KB Output is correct
3 Correct 447 ms 1408 KB Output is correct
4 Correct 267 ms 1408 KB Output is correct
5 Correct 754 ms 2372 KB Output is correct
6 Correct 609 ms 2392 KB Output is correct
7 Correct 509 ms 2424 KB Output is correct
8 Correct 305 ms 2396 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 8056 KB Output is correct
2 Correct 260 ms 7672 KB Output is correct
3 Correct 287 ms 7672 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 353 ms 17144 KB Output is correct
6 Correct 565 ms 17220 KB Output is correct
7 Correct 435 ms 16920 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 1016 KB Output is correct
2 Correct 73 ms 1152 KB Output is correct
3 Correct 202 ms 4196 KB Output is correct
4 Correct 189 ms 4216 KB Output is correct
5 Correct 214 ms 1272 KB Output is correct
6 Correct 359 ms 5368 KB Output is correct
7 Correct 238 ms 1920 KB Output is correct
8 Correct 308 ms 7160 KB Output is correct
9 Correct 1634 ms 18676 KB Output is correct
10 Correct 706 ms 2040 KB Output is correct
11 Correct 1022 ms 3580 KB Output is correct
12 Correct 1725 ms 15376 KB Output is correct
13 Correct 1459 ms 18296 KB Output is correct