제출 #250228

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
250228		errorgorn	케이크 (CEOI14_cake)	C++14	100 / 100	939 ms	32956 KiB

cake

#include <cstdio>
#include <vector>
#include <set>
#include <utility>
using namespace std;
typedef pair<int,int> ii;

struct hull{
    set<ii> s;
    
    inline bool bad(set<ii>::iterator it){
        if (it==--s.end()) return false;
        else return (*next(it)).second<=(*it).second;
    }
    
    inline void add(ii i){
        auto it=s.insert(i).first;
        if (bad(it)){
            s.erase(it);
            return;
        }
        
        while (it!=s.begin() && bad(prev(it))){
            s.erase(prev(it));
        }
    }
    
    inline int query(int i){
        return (*s.lower_bound(ii(i,-1))).second;
    }
}left=*new hull(),right=*new hull();

struct node{
    int s,e,m;
    int val=0;
    node *l,*r;
    
    node (int _s,int _e){
        s=_s,e=_e,m=s+e>>1;
        
        if (s!=e){
            l=new node(s,m);
            r=new node(m+1,e);
        }
    }
    
    void update(int i,int j){
        if (s==e) val=j;
        else{
            if (i<=m) l->update(i,j);
            else r->update(i,j);
            val=max(l->val,r->val);
        }
    }
    
    int query(int i,int j){
        if (s==i && e==j) return val;
        else if (j<=m) return l->query(i,j);
        else if (m<i) return r->query(i,j);
        else return max(l->query(i,m),r->query(m+1,j));
    }
}*root=new node(0,250005);
const int INF=1000000000;

int n,k,q;
int arr[250005];
vector<int> top;

int __w;

void print(){
    for (auto &it:top) printf("%d ",it);
    printf("\n");
    
    for (auto &it:left.s) printf("%d-%d ",it.first,it.second);
    printf("\n");
    
    for (auto &it:right.s) printf("%d-%d ",it.first,it.second);
    printf("\n");
}

void change(int i,int j){
    arr[i]=j;
    root->update(i,j);
    if (i<k) left.add(ii(arr[i],k-i));
    else if (k<i) right.add(ii(arr[i],i-k));
}

int main(){
    scanf("%d%d",&n,&k);
    
    top.resize(10,0);
    __w=n+1;
    for (int x=1;x<=n;x++){
        scanf("%d",&arr[x]);
        if (n-arr[x]<10) top[n-arr[x]]=x;
        root->update(x,arr[x]);
    }
    
    for (int x=k-1;x;x--) left.add(ii(arr[x],k-x));
    left.add(ii(INF,k));
    
    for (int x=k+1;x<=n;x++) right.add(ii(arr[x],x-k));
    right.add(ii(INF,n+1-k));
    
    scanf("%d",&q);
    int a,b;
    while (q--){
        getchar();
        if (getchar()=='E'){
            scanf("%d%d",&a,&b);
            b--;
            for (int x=0;x<10;x++){
                if (top[x]==a){
                    top.erase(top.begin()+x);
                    break;
                }
            }
            
            top.insert(top.begin()+b,a);
            if (top.size()>10) top.pop_back();
            for (int x=b;~x;x--){
                change(top[x],__w++);
            }
            //print();
        }
        else{
            scanf("%d",&a);
            if (a==k){
                printf("0\n");
            }
            else if (a<k){
                printf("%d\n",k-a+right.query(root->query(a,k-1))-1);
            }
            else{
                printf("%d\n",a-k+left.query(root->query(k+1,a))-1);
            }
        }
    }
}

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

cake.cpp: In constructor 'node::node(int, int)':
cake.cpp:39:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         s=_s,e=_e,m=s+e>>1;
                     ~^~
cake.cpp: In function 'int main()':
cake.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&k);
     ~~~~~^~~~~~~~~~~~~~
cake.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&arr[x]);
         ~~~~~^~~~~~~~~~~~~~
cake.cpp:106:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
cake.cpp:111:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d",&a,&b);
             ~~~~~^~~~~~~~~~~~~~
cake.cpp:128:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&a);
             ~~~~~^~~~~~~~~

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