oj.uz

Submission #101448

# Submission time Handle Problem Language Result Execution time Memory
101448 2019-03-19T02:16:24 Z ShaneOng Cake (CEOI14_cake) C++14
0 / 100
 881 ms 30300 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++;
        }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));
                }
            }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:99: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 256 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 445 ms 5584 KB Output isn't correct
2 Incorrect 303 ms 5752 KB Output isn't correct
3 Incorrect 333 ms 5724 KB Output isn't correct
4 Incorrect 295 ms 5660 KB Output isn't correct
5 Incorrect 474 ms 7292 KB Output isn't correct
6 Incorrect 523 ms 7092 KB Output isn't correct
7 Incorrect 383 ms 7408 KB Output isn't correct
8 Incorrect 331 ms 7040 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 106 ms 12048 KB Output isn't correct
2 Incorrect 88 ms 11812 KB Output isn't correct
3 Incorrect 104 ms 11840 KB Output isn't correct
4 Incorrect 3 ms 256 KB Output isn't correct
5 Incorrect 158 ms 27860 KB Output isn't correct
6 Incorrect 138 ms 27768 KB Output isn't correct
7 Incorrect 144 ms 27592 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 1012 KB Output isn't correct
2 Incorrect 37 ms 1220 KB Output isn't correct
3 Incorrect 88 ms 6248 KB Output isn't correct
4 Incorrect 114 ms 6268 KB Output isn't correct
5 Incorrect 121 ms 1900 KB Output isn't correct
6 Incorrect 195 ms 8824 KB Output isn't correct
7 Incorrect 148 ms 3324 KB Output isn't correct
8 Incorrect 263 ms 12552 KB Output isn't correct
9 Incorrect 840 ms 30268 KB Output isn't correct
10 Incorrect 364 ms 4760 KB Output isn't correct
11 Incorrect 603 ms 8056 KB Output isn't correct
12 Incorrect 881 ms 25524 KB Output isn't correct
13 Incorrect 494 ms 30300 KB Output isn't correct