제출 #101852

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
101852		ShaneOng	케이크 (CEOI14_cake)	C++14	0 / 100	1029 ms	26540 KiB

cake

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
int n,st,q,arr[250009],flag;
priority_queue<ii,vector<ii>,greater<ii> > pq[2];
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(){
    //freopen("temp.txt","w",stdout);
    scanf("%d%d",&n,&st);

    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);
            int newnum;
            while(!pq[flag].empty()){
                ii temp=pq[flag].top();
                pq[flag].pop();
                if(temp.second==b-1)
                    continue;
                if((int)pq[flag].size()<=c-1){
                    if((int)pq[flag].size()==c-1)
                        newnum=temp.first;
                    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);
                    arr[temp.second]=temp.first;
                }
                pq[1-flag].push(temp);
            }
            if(b>st)
                root[1]->up(b-1,newnum);
            if(b<st)
                root[0]->up(b-1,newnum);
            pq[1-flag].push(ii(newnum,b-1));
            arr[b-1]=newnum;
            flag=1-flag;
            while((int)pq[flag].size()>10)
                pq[flag].pop();
            ctr++;
            assert((int)pq[flag].size()==min(10,n));
        }else{
            /*for(int x=0;x<n;x++){
                printf("%d ",arr[x]);
            }
            printf("\n");*/

            scanf("%d",&b);
            if(b!=st){
               // printf("%d,%d:",x,b);
                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");
        }
    }


}

컴파일 시 표준 에러 (stderr) 메시지

cake.cpp: In function 'int main()':
cake.cpp:59: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:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&arr[x]);
         ~~~~~^~~~~~~~~~~~~~
cake.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
cake.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c",&a);
         ~~~~~^~~~~~~~~~
cake.cpp:78: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:115:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&b);
             ~~~~~^~~~~~~~~
cake.cpp:99:28: warning: 'newnum' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 root[1]->up(b-1,newnum);
                 ~~~~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50