Submission #101440

#	Time	Username	Problem	Language	Result	Execution time	Memory
101440		cheeheng	Cake (CEOI14_cake)	C++14	50 / 100	2045 ms	15764 KiB

cake

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> ii;

int d[250005];

int o[250005];

int N, a;

set<ii, greater<ii> > di;
set<int> rank1;

void sim(int a){
    int l = a;
    int r = a;
    o[a] = 0;
    int cnt = 1;
    for(int i = 1; i < N; i ++){
        int tempL = l-1;
        int tempR = r+1;
        if(tempL == -1){
            r = tempR;
            o[tempR] = cnt++;
            //printf("o[%d] = %d\n", tempR, cnt-1);
        }else if(tempR == N){
            l = tempL;
            o[tempL] = cnt++;
            //printf("o[%d] = %d\n", tempL, cnt-1);
        }else if(d[tempL] < d[tempR]){
            l = tempL;
            o[tempL] = cnt++;
            //printf("o[%d] = %d\n", tempL, cnt-1);
        }else{
            r = tempR;
            o[tempR] = cnt++;
            //printf("o[%d] = %d\n", tempR, cnt-1);
        }
    }
}

void e(int a, int pos){
    set<int> rank1;

    int cnt = 0;
    //printf("%d\n", pos);
    if(pos != 0){
        for(ii x: di){
            cnt ++;
            rank1.insert(x.second);
            //printf("%d %d\n", x.first, x.second);
            if(cnt == pos){break;}
        }
    }

    if(rank1.count(a)){
        // a is in the top pos
        int min1 = 1e9;
        for(int i: rank1){
            min1 = min(d[i], min1);
        }

        for(int i: rank1){
            if(i != a){
                di.erase(ii(d[i], i));
                di.insert(ii(++d[i], i));
            }else{
                di.erase(ii(d[a], a));
                di.insert(ii(min1, a));
                d[a] = min1;
            }
        }

    }else{
        // a is not in the top pos
        int min1 = 1e9;
        for(int i: rank1){
            min1 = min(d[i], min1);
        }

        for(int i: rank1){
            if(d[i] != min1){
                di.erase(ii(d[i], i));
                di.insert(ii(++d[i], i));
            }
        }

        di.erase(ii(d[a], a));
        di.insert(ii(min1+1, a));
        d[a] = min1+1;
    }

    for(int i = 0; i < N; i ++){
        //printf("d[%d] = %d\n", i, d[i]);
    }
}

int main(){
    scanf("%d%d", &N, &a);

    a --;
    for(int i = 0; i < N; i ++){
        scanf("%d", &d[i]);
        di.insert(ii(d[i], i));
    }

    int cnt = 0;
    for(ii x: di){
        cnt ++;
        rank1.insert(x.second);
        if(cnt == 10){break;}
    }

    int Q;
    scanf("%d", &Q);
    sim(a);
    for(int i = 0; i < Q; i ++){
        char op;
        scanf(" %c", &op);
        if(op == 'F'){
            int x;
            scanf("%d", &x);
            if(N <= 25000 && Q > 100000){
                sim(a);
            }
            printf("%d\n", o[x-1]);
        }else{
            int b, pos;
            scanf("%d%d", &b, &pos);
            e(b-1, pos);
            if(Q <= 100000){
                sim(a);
            }
        }
    }

    return 0;
}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:101: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:105:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &d[i]);
         ~~~~~^~~~~~~~~~~~~
cake.cpp:117:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &Q);
     ~~~~~^~~~~~~~~~
cake.cpp:121:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c", &op);
         ~~~~~^~~~~~~~~~~~
cake.cpp:124:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
             ~~~~~^~~~~~~~~~
cake.cpp:131:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &b, &pos);
             ~~~~~^~~~~~~~~~~~~~~~~~

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