oj.uz

Submission #670748

# Submission time Handle Problem Language Result Execution time Memory
670748 2022-12-10T08:18:41 Z RambaXGorilla Cake (CEOI14_cake) C++17
100 / 100
 1168 ms 24064 KB 
#include<cstdio>
#include<functional>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
const int inf = 1000000000;
int N, A, Q;
int values[250010];
int seg[2][1000010];
map <int,int,greater <int>> indexes;
vector <int> hold;
void buildSeg(int d, int v, int tl, int tr){
    if(tl > tr) return;
    if(tl == tr){
        seg[d][v] = values[tl];
        return;
    }
    int tm = (tl + tr) / 2;
    buildSeg(d, v * 2, tl, tm);
    buildSeg(d, v * 2 + 1, tm + 1, tr);
    seg[d][v] = max(seg[d][v * 2], seg[d][v * 2 + 1]);
}
void updSeg(int d, int p, int x, int v, int tl, int tr){
    if(p == A){
        indexes.erase(values[p]);
        values[p] = x;
        indexes[x] = p;
        return;
    }
    if(p < tl || p > tr) return;
    if(tl == tr){
        indexes.erase(values[p]);
        values[p] = x;
        seg[d][v] = x;
        indexes[x] = p;
        return;
    }
    int tm = (tl + tr) / 2;
    updSeg(d, p, x, v * 2, tl, tm);
    updSeg(d, p, x, v * 2 + 1, tm + 1, tr);
    seg[d][v] = max(seg[d][v * 2], seg[d][v * 2 + 1]);
}
int qrySeg(int d, int l, int r, int v, int tl, int tr){
    if(l > r) return 0;
    if(l == tl && r == tr) return seg[d][v];
    int tm = (tl + tr) / 2;
    return max(qrySeg(d, l, min(r, tm), v * 2, tl, tm), qrySeg(d, max(l, tm + 1), r, v * 2 + 1, tm + 1, tr));
}
int walkSeg(int d, int l, int r, int x, int v, int tl, int tr){
    if(l > r) return -1;
    if(l == tl && r == tr && seg[d][v] < x) return -1;
    if(tl == tr) return tl;
    int tm = (tl + tr) / 2;
    int both[2][7] = {{d, max(l, tm + 1), r, x, v * 2 + 1, tm + 1, tr}, {d, l, min(r, tm), x, v * 2, tl, tm}};
    int first = walkSeg(both[d][0], both[d][1], both[d][2], both[d][3], both[d][4], both[d][5], both[d][6]);
    if(first == -1) first = walkSeg(both[!d][0], both[!d][1], both[!d][2], both[!d][3], both[!d][4], both[!d][5], both[!d][6]);
    return first;
}
int main(){
    scanf("%d%d",&N,&A);
    values[0] = inf;
    values[N + 1] = inf;
    for(int i = 1;i < N + 1;i++){
        scanf("%d",&values[i]);
        indexes[values[i]] = i;
    }
    scanf("%d\n",&Q);
    int rans[2][2] = {{0, A - 1}, {A + 1, N + 1}};
    buildSeg(0, 1, rans[0][0], rans[0][1]);
    buildSeg(1, 1, rans[1][0], rans[1][1]);
    for(int i = 0;i < Q;i++){
        char t;
        scanf("%c ",&t);
        if(t == 'E'){
            int k, e;
            scanf("%d%d\n",&k,&e);
            int cnt = 1;
            int num;
            for(auto j : indexes){
                if(cnt == e){
                    num = j.first + 1;
                    break;
                }
                hold.push_back(j.second);
                cnt++;
            }
            for(int j : hold){
                updSeg(j > A, j, values[j] + 1, 1, rans[j > A][0], rans[j > A][1]);
            }
            updSeg(k > A, k, num, 1, rans[k > A][0], rans[k > A][1]);
            hold.clear();
        }
        else{
            int b;
            scanf("%d\n",&b);
            if(b == A){
                printf("0\n");
                continue;
            }
            int val;
            if(b < A) val = qrySeg(0, b, A - 1, 1, 0, A - 1);
            else val = qrySeg(1, A + 1, b, 1, A + 1, N + 1);
            printf("%d\n",abs(b - walkSeg(b < A, rans[b < A][0], rans[b < A][1], val, 1, rans[b < A][0], rans[b < A][1])) - 1);
        }
    }
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     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]
   66 |         scanf("%d",&values[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~
cake.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     scanf("%d\n",&Q);
      |     ~~~~~^~~~~~~~~~~
cake.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         scanf("%c ",&t);
      |         ~~~~~^~~~~~~~~~
cake.cpp:78:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |             scanf("%d%d\n",&k,&e);
      |             ~~~~~^~~~~~~~~~~~~~~~
cake.cpp:97:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |             scanf("%d\n",&b);
      |             ~~~~~^~~~~~~~~~~
cake.cpp:92:19: warning: 'num' may be used uninitialized in this function [-Wmaybe-uninitialized]
   92 |             updSeg(k > A, k, num, 1, rans[k > A][0], rans[k > A][1]);
      |             ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 17 ms 1072 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 651 ms 5440 KB Output is correct
2 Correct 283 ms 5276 KB Output is correct
3 Correct 438 ms 5268 KB Output is correct
4 Correct 244 ms 5264 KB Output is correct
5 Correct 705 ms 6388 KB Output is correct
6 Correct 525 ms 6936 KB Output is correct
7 Correct 462 ms 6796 KB Output is correct
8 Correct 274 ms 6860 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 8288 KB Output is correct
2 Correct 85 ms 8168 KB Output is correct
3 Correct 83 ms 8076 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 217 ms 18228 KB Output is correct
6 Correct 199 ms 18120 KB Output is correct
7 Correct 126 ms 17940 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 1044 KB Output is correct
2 Correct 44 ms 1120 KB Output is correct
3 Correct 99 ms 4432 KB Output is correct
4 Correct 130 ms 4428 KB Output is correct
5 Correct 176 ms 1760 KB Output is correct
6 Correct 182 ms 6568 KB Output is correct
7 Correct 168 ms 3012 KB Output is correct
8 Correct 262 ms 8908 KB Output is correct
9 Correct 1168 ms 22992 KB Output is correct
10 Correct 573 ms 5188 KB Output is correct
11 Correct 741 ms 7224 KB Output is correct
12 Correct 1126 ms 20032 KB Output is correct
13 Correct 862 ms 24064 KB Output is correct