Submission #101612

#	Time	Username	Problem	Language	Result	Execution time	Memory
101612		rocketninja7	Cake (CEOI14_cake)	C++14	0 / 100	2037 ms	54496 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-1);
    int d[N+1];
    vector<pair<int, int> > best;
    for(int i=1;i<N+1;i++){
        scanf("%d", &d[(i+N-1-a)%N+1]);
        best.push_back(make_pair(-d[(i+N-1-a)%N+1], (i+N-1-a)%N+1));
        if(i==a){
            continue;
        }
        root->update((i+N-1-a)%N+1, d[(i+N-1-a)%N+1]);
    }
    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;
            i=(i+N-1-a)%N+1;
            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;
            }
            b=(b+N-1-a)%N+1;
            if(b==best[0].second){
                printf("%d\n", N-1);
                continue;
            }
            int left=root->query(1, b), right=root->query(b, N-1);
            if(left<right){
                int s=b, e=N;
                while(s<e-1){
                    int m=(s+e)/2;
                    if(root->query(m, N-1)<left){
                        e=m;
                    }
                    else{
                        s=m;
                    }
                }
                printf("%d\n", b-1+N-s);
            }
            else{
                int s=0, e=b;
                while(s<e-1){
                    int m=(s+e)/2;
                    if(root->query(1, m)<right){
                        s=m;
                    }
                    else{
                        e=m;
                    }
                }
                printf("%d\n", s+N-b);
            }
        }
    }
    return 0;
}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:75: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+N-1-a)%N+1]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &Q);
     ~~~~~^~~~~~~~~~
cake.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n%c", &op);
         ~~~~~^~~~~~~~~~~~~
cake.cpp:68: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:100: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