oj.uz

Submission #226237

# Submission time Handle Problem Language Result Execution time Memory
226237 2020-04-23T07:28:01 Z PeppaPig Cake (CEOI14_cake) C++14
73.3333 / 100
 597 ms 15084 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2.5e5;

struct SegmentTree {
    int t[N << 1]; 

    void update(int x, int k) {
        for(t[x += N] = k; x != 1; x >>= 1)
            t[x >> 1] = max(t[x], t[x ^ 1]);
    } 

    int query(int l, int r) {
        int ret = 0;
        for(l += N, r += N + 1; l < r; l >>= 1, r >>= 1) {
            if(l & 1) ret = max(ret, t[l++]);
            if(r & 1) ret = max(ret, t[--r]);
        }
        return ret;
    }

    int pos(int x) {
        int l = 0, r = N - 1;
        while(l < r) {
            int mid = (l + r + 1) >> 1;
            if(query(1, mid) < x) l = mid;
            else r = mid - 1;
        }
        return l;
    }
} L, R;

int n, q, s, A[N];
vector<int> top10;

void add(int i, int x) {
    A[i] = x;
    if(i < s) L.update(s - i, x);
    else R.update(i - s, x);
}

int main() {
    scanf("%d %d", &n, &s);
    for(int i = 1; i <= n; i++) {
        scanf("%d", A + i);
        add(i, A[i]);
        top10.emplace_back(i);
    }
    sort(top10.begin(), top10.end(), [&](int a, int b) {
        return A[a] > A[b];
    });
    while(top10.size() > 10) top10.pop_back();
    L.update(s, 1e9), R.update(n - s + 1, 1e9);

    scanf("%d", &q);
    for(int i = 1, a, b, ptr = n; i <= q; i++) {
        char c;
        scanf(" %c %d", &c, &a);
        if(c == 'E') {
            scanf("%d", &b), --b;

            auto it = find(top10.begin(), top10.end(), a);
            if(it != top10.end()) top10.erase(it);
            top10.insert(top10.begin() + b, a);

            for(int j = b; ~j; j--) add(top10[j], ++ptr);

            while(top10.size() > 10) top10.pop_back();
        } else {
            if(a == s) printf("0\n");
            else if(a < s) printf("%d\n", (s - a) + R.pos(L.query(1, s - a)));
            else printf("%d\n", (a - s) + L.pos(R.query(1, a - s)));
        }
    }

    return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &s);
     ~~~~~^~~~~~~~~~~~~~~~~
cake.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", A + i);
         ~~~~~^~~~~~~~~~~~~
cake.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
cake.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c %d", &c, &a);
         ~~~~~^~~~~~~~~~~~~~~~~~
cake.cpp:62:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &b), --b;
             ~~~~~~~~~~~~~~~^~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 8 ms 512 KB Output is correct
5 Correct 15 ms 768 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 5132 KB Output is correct
2 Correct 198 ms 5112 KB Output is correct
3 Correct 202 ms 5112 KB Output is correct
4 Correct 172 ms 5112 KB Output is correct
5 Correct 250 ms 5624 KB Output is correct
6 Correct 237 ms 5880 KB Output is correct
7 Correct 214 ms 5880 KB Output is correct
8 Correct 181 ms 6008 KB Output is correct

Subtask #3
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 4080 KB Output is correct
2 Correct 115 ms 3952 KB Output is correct
3 Correct 112 ms 3952 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Incorrect 180 ms 7632 KB Output isn't correct
6 Incorrect 185 ms 7672 KB Output isn't correct
7 Incorrect 127 ms 7656 KB Output isn't correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 1016 KB Output is correct
2 Correct 40 ms 1152 KB Output is correct
3 Correct 83 ms 2548 KB Output is correct
4 Correct 95 ms 2548 KB Output is correct
5 Correct 114 ms 1912 KB Output is correct
6 Correct 131 ms 3700 KB Output is correct
7 Correct 141 ms 2680 KB Output is correct
8 Correct 119 ms 4592 KB Output is correct
9 Runtime error 297 ms 15084 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Correct 364 ms 5240 KB Output is correct
11 Correct 385 ms 6520 KB Output is correct
12 Correct 597 ms 11376 KB Output is correct
13 Incorrect 508 ms 13036 KB Output isn't correct