oj.uz

답안 #101463

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101463 2019-03-19T02:45:58 Z ShaneOng 케이크 (CEOI14_cake) C++14
0 / 100
 216 ms 49596 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.second==b-1)
                    continue;
                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:103: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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 2304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 8 ms 2432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 7 ms 2448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 9 ms 2432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 12 ms 5248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 13 ms 5504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 13 ms 5376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 13 ms 5376 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 107 ms 10872 KB Output isn't correct
2 Runtime error 48 ms 20168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 41 ms 20088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Incorrect 3 ms 384 KB Output isn't correct
5 Incorrect 160 ms 25464 KB Output isn't correct
6 Runtime error 107 ms 49544 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 97 ms 49372 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 8 ms 1408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 78 ms 10416 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 24 ms 10368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 5 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 52 ms 13432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 12 ms 2588 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 44 ms 20088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 216 ms 49596 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 4 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 19 ms 4480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 111 ms 39684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 107 ms 49500 KB Execution killed with signal 11 (could be triggered by violating memory limits)