답안 #101532

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101532 2019-03-19T03:46:14 Z shenxy 케이크 (CEOI14_cake) C++11
0 / 100
1572 ms 27568 KB
#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 getsign(int X) {
    if (X == 0) return 0;
    return X > 0 ? 1 : -1;
}
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

cake.cpp: In function 'int main()':
cake.cpp:43: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:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &nextint);
         ~~~~~^~~~~~~~~~~~~~~~
cake.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &Q);
     ~~~~~^~~~~~~~~~
cake.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c", &c);
         ~~~~~^~~~~~~~~~~
cake.cpp:64: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:71:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &id);
             ~~~~~^~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 356 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 359 ms 1356 KB Output isn't correct
2 Incorrect 262 ms 1504 KB Output isn't correct
3 Correct 287 ms 1420 KB Output is correct
4 Correct 158 ms 1508 KB Output is correct
5 Incorrect 458 ms 3052 KB Output isn't correct
6 Incorrect 397 ms 3072 KB Output isn't correct
7 Correct 299 ms 3072 KB Output is correct
8 Correct 159 ms 2996 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 451 ms 11148 KB Output isn't correct
2 Incorrect 249 ms 11120 KB Output isn't correct
3 Incorrect 210 ms 10984 KB Output isn't correct
4 Incorrect 2 ms 256 KB Output isn't correct
5 Incorrect 381 ms 26568 KB Output isn't correct
6 Incorrect 494 ms 26612 KB Output isn't correct
7 Incorrect 319 ms 26312 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 55 ms 796 KB Output isn't correct
2 Correct 76 ms 1120 KB Output is correct
3 Correct 168 ms 5764 KB Output is correct
4 Incorrect 176 ms 5804 KB Output isn't correct
5 Incorrect 169 ms 860 KB Output isn't correct
6 Correct 391 ms 7600 KB Output is correct
7 Correct 219 ms 1964 KB Output is correct
8 Correct 221 ms 10864 KB Output is correct
9 Incorrect 1572 ms 27568 KB Output isn't correct
10 Incorrect 487 ms 1644 KB Output isn't correct
11 Incorrect 963 ms 4036 KB Output isn't correct
12 Incorrect 1481 ms 22448 KB Output isn't correct
13 Incorrect 1346 ms 27520 KB Output isn't correct