제출 #101666

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

cake

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

struct node{
    int s, e, m, v;
    node *l, *r;
    node(int _s, int _e): s(_s), e(_e), m((_s+_e)/2), v(0){
        if(s<e){
            l=new node(s, m);
            r=new node(m+1, e);
        }
    }
    void update(int i, int val){
        if(s==i&&e==i){
            v=val;
        }
        else{
            if(i<=m){
                l->update(i, val);
            }
            else{
                r->update(i, val);
            }
            v=max(l->v, r->v);
        }
    }
    int query(int si, int ei){
        if(s==si&&e==ei){
            return v;
        }
        if(ei<=m){
            return l->query(si, ei);
        }
        if(si>m){
            return r->query(si, ei);
        }
        return max(l->query(si, m), r->query(m+1, ei));
    }
};

int main(){
    int N, a;
    scanf("%d%d", &N, &a);
    node *root=new node(1, N);
    int d[N+1];
    vector<pair<int, int> > best;
    for(int i=1;i<N+1;i++){
        scanf("%d", &d[i]);
        best.push_back(make_pair(-d[i], i));
        root->update(i, d[i]);
    }
    sort(best.begin(), best.end());
    while(best.size()>10){
        best.pop_back();
    }
    int Q;
    scanf("%d", &Q);
    while(Q--){
        char op;
        scanf("\n%c", &op);
        if(op=='E'){
            int i, e;
            scanf("%d%d", &i, &e);
            if(N==1){
                continue;
            }
            int tempE=e;
            e--;
            for(int j=0;j<best.size();j++){
                if(best[j].second==i){
                    best.erase(best.begin()+j);
                }
            }
            int j=0;
            while(e--){
                --best[j].first;
                root->update(best[j].second, ++d[best[j].second]);
                j++;
            }
            if(tempE>1){
                d[i]=d[best[j-1].second]-1;
            }
            else{
                d[i]=d[best[j].second]+1;
            }
            root->update(i, d[i]);
            best.insert(best.begin()+tempE-1, make_pair(-d[i], i));
            if(best.size()>10){
                best.erase(--best.end());
            }
        }
        else{
            int b;
            scanf("%d", &b);
            if(b==a){
                printf("0\n");
                continue;
            }
            if(b<a){
                int left=root->query(b, a);
                int s=a, e=N+1;
                while(s<e-1){
                    int m=(s+e)/2;
                    if(root->query(a, m)<left){
                        s=m;
                    }
                    else{
                        e=m;
                    }
                }
                //printf("1. %d, %d\n", b, s);
                printf("%d\n", s-b);
            }
            else{
                int right=root->query(a, b);
                int s=1, e=a+1;
                while(s<e-1){
                    int m=(s+e)/2;
                    if(root->query(m, a)<right){
                        e=m;
                    }
                    else{
                        s=m;
                    }
                }
                //printf("2. %d, %d\n", b, s);
                printf("%d\n", b-s);
            }
        }
    }
    return 0;
}

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

cake.cpp: In function 'int main()':
cake.cpp:71:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<best.size();j++){
                         ~^~~~~~~~~~~~
cake.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &a);
     ~~~~~^~~~~~~~~~~~~~~~
cake.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &d[i]);
         ~~~~~^~~~~~~~~~~~~
cake.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &Q);
     ~~~~~^~~~~~~~~~
cake.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n%c", &op);
         ~~~~~^~~~~~~~~~~~~
cake.cpp:65:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &i, &e);
             ~~~~~^~~~~~~~~~~~~~~~
cake.cpp:96: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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50