oj.uz

Submission #101440

# Submission time Handle Problem Language Result Execution time Memory
101440 2019-03-19T02:03:07 Z cheeheng Cake (CEOI14_cake) C++14
50 / 100
 2000 ms 15764 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 256 KB Output is correct
3 Correct 3 ms 256 KB Output is correct
4 Correct 12 ms 384 KB Output is correct
5 Correct 111 ms 956 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 755 ms 856 KB Output is correct
2 Correct 392 ms 896 KB Output is correct
3 Correct 391 ms 1016 KB Output is correct
4 Correct 242 ms 896 KB Output is correct
5 Correct 813 ms 1784 KB Output is correct
6 Correct 679 ms 1756 KB Output is correct
7 Correct 604 ms 1784 KB Output is correct
8 Correct 376 ms 1784 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 6396 KB Output is correct
2 Correct 85 ms 6236 KB Output is correct
3 Correct 88 ms 6264 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 392 ms 14780 KB Output is correct
6 Correct 354 ms 14684 KB Output is correct
7 Correct 183 ms 14584 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 688 KB Output is correct
2 Correct 269 ms 836 KB Output is correct
3 Execution timed out 2045 ms 3504 KB Time limit exceeded
4 Execution timed out 2036 ms 3428 KB Time limit exceeded
5 Correct 392 ms 760 KB Output is correct
6 Incorrect 201 ms 4308 KB Output isn't correct
7 Correct 1570 ms 1536 KB Output is correct
8 Incorrect 309 ms 5880 KB Output isn't correct
9 Incorrect 1359 ms 15764 KB Output isn't correct
10 Correct 1309 ms 1680 KB Output is correct
11 Execution timed out 2033 ms 1912 KB Time limit exceeded
12 Incorrect 1430 ms 13176 KB Output isn't correct
13 Incorrect 960 ms 15736 KB Output isn't correct