답안 #101460

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101460 2019-03-19T02:41:46 Z ShaneOng 케이크 (CEOI14_cake) C++14
0 / 100
776 ms 26480 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);
            if((int)pq[flag].size()==10)
                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)));
                    int temp=-1;
                    if(st!=1)
                        temp=(root[0]->bs2(root[1]->qu(st,b-1)));
                    printf("%d\n",((b-1)-temp-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)));
                    int temp=n;
                    if(st!=n)
                        temp=root[1]->bs1(root[0]->qu(b-1,st-2));
                    printf("%d\n",(temp-(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:101:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&b);
             ~~~~~^~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 417 ms 1248 KB Output isn't correct
2 Incorrect 348 ms 1280 KB Output isn't correct
3 Incorrect 340 ms 1528 KB Output isn't correct
4 Incorrect 245 ms 1280 KB Output isn't correct
5 Incorrect 483 ms 2776 KB Output isn't correct
6 Incorrect 387 ms 2908 KB Output isn't correct
7 Incorrect 382 ms 2816 KB Output isn't correct
8 Incorrect 253 ms 2816 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 108 ms 10672 KB Output isn't correct
2 Incorrect 73 ms 10616 KB Output isn't correct
3 Incorrect 69 ms 10620 KB Output isn't correct
4 Runtime error 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Incorrect 132 ms 25464 KB Output isn't correct
6 Incorrect 138 ms 25592 KB Output isn't correct
7 Incorrect 139 ms 25128 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 36 ms 760 KB Output isn't correct
2 Incorrect 53 ms 896 KB Output isn't correct
3 Incorrect 81 ms 5368 KB Output isn't correct
4 Incorrect 109 ms 5496 KB Output isn't correct
5 Incorrect 122 ms 888 KB Output isn't correct
6 Incorrect 180 ms 7232 KB Output isn't correct
7 Incorrect 145 ms 1944 KB Output isn't correct
8 Incorrect 206 ms 10272 KB Output isn't correct
9 Incorrect 772 ms 26480 KB Output isn't correct
10 Incorrect 360 ms 1656 KB Output isn't correct
11 Incorrect 458 ms 3688 KB Output isn't correct
12 Incorrect 776 ms 21700 KB Output isn't correct
13 Incorrect 550 ms 26360 KB Output isn't correct