Submission #670748

#	Time	Username	Problem	Language	Result	Execution time	Memory
670748		RambaXGorilla	Cake (CEOI14_cake)	C++17	100 / 100	1168 ms	24064 KiB

cake

#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 (stderr)

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 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50