Submission #57864

#	Time	Username	Problem	Language	Result	Execution time	Memory
57864		gabrielsimoes	Cake (CEOI14_cake)	C++17	100 / 100	495 ms	72740 KiB

cake

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 250010, MAXQ = 500010;
typedef pair<int, int> pii;

struct Bit {
    int sz;
    vector<int> v;

    Bit() : sz(0), v(MAXN) {};

    void resize(int x) {
        sz = x;
    }

    int get(int pos) {
        int ret = 0;
        while (pos > 0) {
            ret = max(ret, v[pos]);
            pos -= pos&-pos;
        }
        return ret;
    }

    void update(int pos, int val) {
        while (pos <= sz) {
            v[pos] = max(v[pos], val);
            pos += pos&-pos;
        }
    }

    int find(int val) {
        int ret = 0;
        for (int i = 20; i >= 0; i--) {
            int nx = ret + (1 << i);
            if (nx <= sz && v[nx] < val) {
                ret = nx;
            }
        }
        return ret;
    }
} l, r;

int n, start;
int d[MAXN];

int inTop10[MAXN];
int top_change = 0;
vector<pii> top10;

int main() {
    scanf("%d%d", &n, &start);
    for (int i = 1; i <= n; i++)
        scanf("%d", &d[i]);

    for (int i = 1; i <= n; i++)
        top10.push_back({d[i], i});

    l.resize(start - 1);
    r.resize(n - start);

    for (int i = start-1; i >= 1; i--) {
        l.update(start - i, d[i]);
    }

    for (int i = start+1; i <= n; i++) {
        r.update(i - start, d[i]);
    }

    sort(top10.rbegin(), top10.rend());
    top10.resize(min(n, 10));
    memset(inTop10, -1, sizeof(inTop10));
    for (int i = 0; i < top10.size(); i++)
        inTop10[top10[i].second] = i;

    top_change = n+1;

    char c;
    int nq, x, y;
    scanf("%d", &nq);
    while (nq--) {
        scanf(" %c", &c);
        if (c == 'E') {
            scanf("%d%d", &x, &y);

            if (inTop10[x] != -1) {
                top10.erase(top10.begin() + inTop10[x]);
                inTop10[x] = -1;
            }

            for (pii p : top10) inTop10[p.second] = -1;

            top10.insert(top10.begin() + (y-1), {-1, x});
            top10.resize(min(n, 10));

            for (int i = int(top10.size()) - 1; i >= 0; i--) {
                pii &p = top10[i];

                // printf("changing pos %d to %d\n", p.second, top_change);
                p.first = top_change++;
                inTop10[p.second] = i;

                if (p.second < start) l.update(start - p.second, p.first);
                if (p.second > start) r.update(p.second - start, p.first);
            }
        } else {
            scanf("%d", &x);

            if (x == start) {
                printf("%d\n", 0);
                continue;
            }

            int pos = abs(start - x), mx, cnt;
            if (x < start) {
                mx = l.get(pos);
                cnt = r.find(mx+1);
            } else {
                mx = r.get(pos);
                cnt = l.find(mx+1);
            }

            // printf("pos %d (%c) mx %d cnt %d\n", pos, x < start ? 'l' : 'r', mx, cnt);

            printf("%d\n", pos + cnt);
        }
    }
}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:74:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < top10.size(); i++)
                     ~~^~~~~~~~~~~~~~
cake.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &start);
     ~~~~~^~~~~~~~~~~~~~~~~~~~
cake.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &d[i]);
         ~~~~~^~~~~~~~~~~~~
cake.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &nq);
     ~~~~~^~~~~~~~~~~
cake.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c", &c);
         ~~~~~^~~~~~~~~~~
cake.cpp:85:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~
cake.cpp:108:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
             ~~~~~^~~~~~~~~~

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