oj.uz

답안 #101613

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101613 2019-03-19T05:14:56 Z shenxy 케이크 (CEOI14_cake) C++11
0 / 100
 190 ms 51636 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 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') {
          	throw(5);
            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: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:61: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:68: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.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 9 ms 2560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 8 ms 2816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 11 ms 2800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 9 ms 2816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 19 ms 5632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 9 ms 5760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 16 ms 5760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 17 ms 5760 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 78 ms 21100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 60 ms 21040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 75 ms 21100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 2 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 144 ms 51540 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 170 ms 51636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 160 ms 51476 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 5 ms 1536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 31 ms 10868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 30 ms 10876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 4 ms 884 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 40 ms 13940 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 6 ms 2736 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 70 ms 20956 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 160 ms 51520 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 4 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 17 ms 4732 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 121 ms 41312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 190 ms 51600 KB Execution killed with signal 11 (could be triggered by violating memory limits)