oj.uz

Submission #226238

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

using namespace std;

const int N = 3e5;

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 9 ms 512 KB Output is correct
5 Correct 16 ms 768 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 1016 KB Output is correct
2 Correct 194 ms 896 KB Output is correct
3 Correct 200 ms 1016 KB Output is correct
4 Correct 175 ms 896 KB Output is correct
5 Correct 240 ms 1152 KB Output is correct
6 Correct 227 ms 1152 KB Output is correct
7 Correct 215 ms 1152 KB Output is correct
8 Correct 179 ms 1152 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 2924 KB Output is correct
2 Correct 125 ms 2924 KB Output is correct
3 Correct 106 ms 2800 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 194 ms 5484 KB Output is correct
6 Correct 183 ms 5356 KB Output is correct
7 Correct 142 ms 5096 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 888 KB Output is correct
2 Correct 45 ms 888 KB Output is correct
3 Correct 92 ms 1884 KB Output is correct
4 Correct 86 ms 1780 KB Output is correct
5 Correct 113 ms 1020 KB Output is correct
6 Correct 131 ms 2292 KB Output is correct
7 Correct 139 ms 1372 KB Output is correct
8 Correct 120 ms 2544 KB Output is correct
9 Correct 607 ms 8684 KB Output is correct
10 Correct 378 ms 1784 KB Output is correct
11 Correct 399 ms 2704 KB Output is correct
12 Correct 602 ms 5608 KB Output is correct
13 Correct 498 ms 6356 KB Output is correct