oj.uz

Submission #101452

# Submission time Handle Problem Language Result Execution time Memory
101452 2019-03-19T02:30:17 Z ShaneOng Cake (CEOI14_cake) C++14
0 / 100
 868 ms 28152 KB 
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
int n,st,q,arr[250009],flag;
struct node{
    int s,e,m,v=0;
    node *l,*r;
    node(int a,int b){
        s=a,e=b,m=(s+e)/2;
        if(s!=e){
            l=new node(s,m);
            r=new node(m+1,e);
            v=max(l->v,r->v);
        }else{
            v=arr[s];
        }

    }
    void up(int a,int b){
        if(s==e&&s==a){
            v=b;
            return;
        }
        if(a<=m)
            l->up(a,b);
        else
            r->up(a,b);

        v=max(l->v,r->v);
    }
    int qu(int a,int b){
        if(s==a&&b==e){
            return v;
        }
        if(b<=m)
            return l->qu(a,b);
        if(a>m)
            return r->qu(a,b);
        return max(l->qu(a,m),r->qu(m+1,e));
    }
    int bs1(int a){
        if(s==e)
            return s+(v<a);
        if(a>l->v)
            return r->bs1(a);
        return l->bs1(a);
    }
    int bs2(int a){
        if(s==e)
            return s+(v<a);
        if(a>r->v)
            return l->bs1(a);
        return r->bs1(a);
    }
}*root[2];
int main(){
    scanf("%d%d",&n,&st);
    priority_queue<ii,vector<ii>,greater<ii> > pq[2];
    for(int x=0;x<n;x++){
        scanf("%d",&arr[x]);
        if(arr[x]>n-10)
            pq[flag].push(ii(arr[x],x));
    }
    int ctr=n;
    if(st>1)
        root[0]=new node(0,st-2);
    if(st<n)
        root[1]=new node(st,n-1);

    scanf("%d",&q);
    for(int x=0,b,c;x<q;x++){
        char a;
        scanf(" %c",&a);

        if(a=='E'){
            scanf("%d%d",&b,&c);
            pq[flag].pop();
            while(!pq[flag].empty()){
                ii temp=pq[flag].top();
                pq[flag].pop();
                if(temp.first>ctr-c+1){
                    temp.first++;
                    if(temp.second+1>st){
                        root[1]->up(temp.second,temp.first);
                    }
                    if(temp.second+1<st)
                        root[0]->up(temp.second,temp.first);
                }
                pq[1-flag].push(temp);
            }
            if(b>st)
                root[1]->up(b-1,ctr-c+2);
            if(b<st)
                root[0]->up(b-1,ctr-c+2);
            pq[1-flag].push(ii(ctr-c+2,b-1));
            flag=1-flag;
            ctr++;
            assert((int)pq[flag].size()==min(10,n));
        }else{
            scanf("%d",&b);
            if(b!=st){

                if(b>st){
                    //printf("%d,%d\n",root[1]->qu(st,b-1),root[0]->bs2(root[1]->qu(st,b-1)));
                    printf("%d\n",((b-1)-(root[0]->bs2(root[1]->qu(st,b-1)))-1));
                }
                if(b<st){
                    //printf("%d,%d\n",root[0]->qu(b-1,st-2),root[1]->bs1(root[0]->qu(b-1,st-2)));

                    printf("%d\n",(root[1]->bs1(root[0]->qu(b-1,st-2))-(b-1)-1));
                }
            }else
                printf("0\n");
        }
    }


}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&st);
     ~~~~~^~~~~~~~~~~~~~~
cake.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&arr[x]);
         ~~~~~^~~~~~~~~~~~~~
cake.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
cake.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c",&a);
         ~~~~~^~~~~~~~~~
cake.cpp:76:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d",&b,&c);
             ~~~~~^~~~~~~~~~~~~~
cake.cpp:100:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&b);
             ~~~~~^~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 410 ms 2296 KB Output isn't correct
2 Incorrect 284 ms 2268 KB Output isn't correct
3 Incorrect 362 ms 2372 KB Output isn't correct
4 Incorrect 268 ms 2220 KB Output isn't correct
5 Incorrect 453 ms 3832 KB Output isn't correct
6 Incorrect 435 ms 4368 KB Output isn't correct
7 Incorrect 427 ms 3944 KB Output isn't correct
8 Incorrect 301 ms 4332 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 114 ms 11620 KB Output isn't correct
2 Incorrect 89 ms 11428 KB Output isn't correct
3 Incorrect 89 ms 11384 KB Output isn't correct
4 Incorrect 3 ms 384 KB Output isn't correct
5 Incorrect 154 ms 26288 KB Output isn't correct
6 Incorrect 145 ms 26360 KB Output isn't correct
7 Incorrect 136 ms 26232 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 1016 KB Output isn't correct
2 Incorrect 37 ms 1280 KB Output isn't correct
3 Incorrect 106 ms 6312 KB Output isn't correct
4 Incorrect 112 ms 6264 KB Output isn't correct
5 Incorrect 123 ms 1844 KB Output isn't correct
6 Incorrect 171 ms 8184 KB Output isn't correct
7 Incorrect 143 ms 2680 KB Output isn't correct
8 Incorrect 192 ms 11128 KB Output isn't correct
9 Incorrect 868 ms 27992 KB Output isn't correct
10 Incorrect 418 ms 3244 KB Output isn't correct
11 Incorrect 625 ms 4604 KB Output isn't correct
12 Incorrect 802 ms 23236 KB Output isn't correct
13 Incorrect 499 ms 28152 KB Output isn't correct