Submission #101539

#	Time	Username	Problem	Language	Result	Execution time	Memory
101539		shenxy	Cake (CEOI14_cake)	C++11	0 / 100	1617 ms	29548 KiB

cake

#include <cstdio>
#include <algorithm>
#include <queue>
#include <utility>
using namespace std;
typedef pair<int, int> ii;
struct segnode {
    int first, last, middle, maxval;
    segnode *l, *r;
    segnode(int s, int e) {
        first = s;
        last = e;
        middle = (first + last) / 2;
        maxval = 0;
        if (first != last) {
            l = new segnode(first, middle);
            r = new segnode(middle + 1, last);
        }
    }
    void point_update(int i, int x) {
        if (first == last) {
            maxval = x;
            return;
        }
        if (i > middle) r -> point_update(i, x);
        else l -> point_update(i, x);
        maxval = max(l -> maxval, r -> maxval);
    }
    int rangemaxq(int a, int b) {
        if (first == a && last == b) return maxval;
        if (a > middle) return r -> rangemaxq(a, b);
        if (b <= middle) return l -> rangemaxq(a, b);
        return max(l -> rangemaxq(a, middle), r -> rangemaxq(middle + 1, b));
    }
} *root;
int main() {
    //freopen("cakein.txt", "r", stdin);
    int N, a, nextint;
    scanf("%d %d", &N, &a);
    root = new segnode(1, N);
    priority_queue<ii> topten;
    for (int i = 1; i <= N; i++) {
        scanf("%d", &nextint);
        if (i != a) {
            root -> point_update(i, nextint);
            topten.push(ii(nextint, i));
        }
    }
    int realtop[10];
    for (int i = 0; i < 10; i++) {
        realtop[i] = topten.top().second;
        topten.pop();
    }
    int Q, id, b;
    char c;
    scanf("%d", &Q);
    for (int i = 0; i < Q; i++) {
        scanf(" %c", &c);
        if (c == 'E') {
            scanf("%d %d", &id, &b);
            for (int j = 0; j < b - 1; j++) root -> point_update(realtop[j], root -> rangemaxq(realtop[j], realtop[j]) + 1);
            for (int j = b; j < 10; j++) realtop[j] = realtop[j - 1];
            realtop[b - 1] = id;
            if (b != 10) root -> point_update(id, root -> rangemaxq(realtop[b], realtop[b]) + 1);
            else root -> point_update(id, root -> rangemaxq(realtop[b - 2], realtop[b - 2]) - 1);
        } else {
            scanf("%d", &id);
            if (id == a) {
                printf("0\n");
                continue;
            } else if (id > a) {
                int bstaval = root -> rangemaxq(a + 1, id);
                int lower = 1, upper = a - 1;
                while (lower < upper) {
                    int midval = (lower + upper) / 2;
                    if (root -> rangemaxq(a - midval, a - 1) < bstaval) lower = midval + 1;
                    else upper = midval;
                }
                if (root -> rangemaxq(1, a - 1) < bstaval) lower = a;
                printf("%d\n", lower - 1 + id - a);
            } else {
                int bstaval = root -> rangemaxq(id, a - 1);
                int lower = 1, upper = N - a;
                while (lower < upper) {
                    int midval = (lower + upper) / 2;
                    if (root -> rangemaxq(a + 1, a + midval) < bstaval) lower = midval + 1;
                    else upper = midval;
                }
                if (root -> rangemaxq(a + 1, N) < bstaval) lower = N - a + 1;
                printf("%d\n", lower - 1 + a - id);
            }
        }
    }
    return 0;
}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:39: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:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &nextint);
         ~~~~~^~~~~~~~~~~~~~~~
cake.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &Q);
     ~~~~~^~~~~~~~~~
cake.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c", &c);
         ~~~~~^~~~~~~~~~~
cake.cpp:60:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &id, &b);
             ~~~~~^~~~~~~~~~~~~~~~~~
cake.cpp:67:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &id);
             ~~~~~^~~~~~~~~~~

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