Submission #101807

#	Time	Username	Problem	Language	Result	Execution time	Memory
101807		rocketninja7	Cake (CEOI14_cake)	C++14	100 / 100	957 ms	28516 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 index, int val){
        if(s==e){
            v=val;
        }
        else{
            if(index<=m){
                l->update(index, val);
            }
            else{
                r->update(index, val);
            }
            v=max(l->v, r->v);
        }
    }
    int query(int si, int ei){
        if(si==s&&ei==e){
            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 query2(int val, int dir){
        if(s==e){
            return s;
        }
        if(dir==1){
            if(l->v<val){
                return r->query2(val, dir);
            }
            return l->query2(val, dir);
        }
        if(r->v<val){
            return l->query2(val, dir);
        }
        return r->query2(val, dir);
    }
};

int main(){
    int N, a;
    scanf("%d%d", &N, &a);
    int d[N+1];
    vector<pair<int, int> > best;
    node *lst=new node(0, a-1);
    node *rst=new node(a+1, N+1);
    for(int i=1;i<N+1;i++){
        scanf("%d", &d[i]);
        best.push_back(make_pair(-d[i], i));
        if(i<a){
            lst->update(i, d[i]);
        }
        else{
            rst->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;
            }
            e--;
            for(int j=0;j<best.size();j++){
                if(best[j].first==-d[i]){
                    best.erase(best.begin()+j);
                    break;
                }
            }
            for(int j=0;j<e;j++){
                if(best[j].second<a){
                    lst->update(best[j].second, -(--best[j].first));
                }
                else if(best[j].second>a){
                    rst->update(best[j].second, -(--best[j].first));
                }
                else{
                    --best[j].first;
                }
                d[best[j].second]++;
            }
            d[i]=(e>0?d[best[e-1].second]-1:d[best[e].second]+1);
            best.insert(best.begin()+e, make_pair(-d[i], i));
            if(best.size()>10){
                best.pop_back();
            }
            if(i<a){
                lst->update(i, d[i]);
            }
            else if(i>a){
                rst->update(i, d[i]);
            }
        }
        else{
            int b;
            scanf("%d", &b);
            if(b<a){
                printf("%d\n", rst->query2(lst->query(b, a-1), 1)-1-b);
            }
            else if(b>a){
                printf("%d\n", b-1-lst->query2(rst->query(a+1, b), -1));
            }
            else{
                printf("0\n");
            }
        }
    }
    return 0;
}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:91:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<best.size();j++){
                         ~^~~~~~~~~~~~
cake.cpp:60: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:66:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &d[i]);
         ~~~~~^~~~~~~~~~~~~
cake.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &Q);
     ~~~~~^~~~~~~~~~
cake.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n%c", &op);
         ~~~~~^~~~~~~~~~~~~
cake.cpp:86: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:123:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &b);
             ~~~~~^~~~~~~~~~

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