oj.uz

Submission #101443

# Submission time Handle Problem Language Result Execution time Memory
101443 2019-03-19T02:08:53 Z cheeheng Cake (CEOI14_cake) C++14
50 / 100
 2000 ms 14716 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 || N > 25000){
                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 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 256 KB Output is correct
4 Correct 12 ms 384 KB Output is correct
5 Correct 104 ms 1144 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 691 ms 896 KB Output is correct
2 Correct 413 ms 988 KB Output is correct
3 Correct 389 ms 1016 KB Output is correct
4 Correct 240 ms 1016 KB Output is correct
5 Correct 798 ms 1788 KB Output is correct
6 Correct 621 ms 1664 KB Output is correct
7 Correct 456 ms 1756 KB Output is correct
8 Correct 301 ms 1784 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 6520 KB Output is correct
2 Correct 93 ms 6264 KB Output is correct
3 Correct 86 ms 6236 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 365 ms 14712 KB Output is correct
6 Correct 409 ms 14716 KB Output is correct
7 Correct 194 ms 14500 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 712 KB Output is correct
2 Correct 293 ms 640 KB Output is correct
3 Execution timed out 2049 ms 3496 KB Time limit exceeded
4 Execution timed out 2045 ms 3400 KB Time limit exceeded
5 Correct 419 ms 792 KB Output is correct
6 Execution timed out 2033 ms 4348 KB Time limit exceeded
7 Correct 1806 ms 1416 KB Output is correct
8 Execution timed out 2027 ms 5752 KB Time limit exceeded
9 Execution timed out 2047 ms 14328 KB Time limit exceeded
10 Correct 1421 ms 1704 KB Output is correct
11 Execution timed out 2041 ms 1912 KB Time limit exceeded
12 Execution timed out 2036 ms 11620 KB Time limit exceeded
13 Execution timed out 2051 ms 14328 KB Time limit exceeded