답안 #101775

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101775 2019-03-20T03:50:55 Z ShaneOng 케이크 (CEOI14_cake) C++14
0 / 100
904 ms 29128 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,b));
    }
    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->bs2(a);
        return r->bs2(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);
 
            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;
            while((int)pq[flag].size()>10)
                pq[flag].pop();
            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:105:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&b);
             ~~~~~^~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 2 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 404 ms 4252 KB Output isn't correct
2 Correct 287 ms 4600 KB Output is correct
3 Correct 359 ms 4680 KB Output is correct
4 Correct 248 ms 4600 KB Output is correct
5 Incorrect 531 ms 6040 KB Output isn't correct
6 Correct 498 ms 6008 KB Output is correct
7 Correct 415 ms 6244 KB Output is correct
8 Correct 316 ms 6088 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 12036 KB Output is correct
2 Correct 98 ms 11896 KB Output is correct
3 Correct 81 ms 11928 KB Output is correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Correct 192 ms 27568 KB Output is correct
6 Incorrect 185 ms 27512 KB Output isn't correct
7 Correct 106 ms 27352 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 47 ms 1188 KB Output isn't correct
2 Correct 37 ms 1252 KB Output is correct
3 Correct 90 ms 6268 KB Output is correct
4 Correct 124 ms 6264 KB Output is correct
5 Incorrect 133 ms 1912 KB Output isn't correct
6 Correct 178 ms 8788 KB Output is correct
7 Correct 144 ms 3336 KB Output is correct
8 Correct 208 ms 12284 KB Output is correct
9 Incorrect 885 ms 29088 KB Output isn't correct
10 Incorrect 372 ms 3832 KB Output isn't correct
11 Correct 542 ms 6632 KB Output is correct
12 Correct 904 ms 24048 KB Output is correct
13 Incorrect 622 ms 29128 KB Output isn't correct