oj.uz

Submission #231098

# Submission time Handle Problem Language Result Execution time Memory
231098 2020-05-12T17:01:34 Z DodgeBallMan Cake (CEOI14_cake) C++14
100 / 100
 610 ms 12508 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 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 233 ms 5112 KB Output is correct
2 Correct 200 ms 5240 KB Output is correct
3 Correct 211 ms 5112 KB Output is correct
4 Correct 174 ms 5116 KB Output is correct
5 Correct 247 ms 5624 KB Output is correct
6 Correct 226 ms 5908 KB Output is correct
7 Correct 217 ms 5752 KB Output is correct
8 Correct 184 ms 5884 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 4076 KB Output is correct
2 Correct 117 ms 3952 KB Output is correct
3 Correct 110 ms 3952 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 190 ms 7660 KB Output is correct
6 Correct 183 ms 7532 KB Output is correct
7 Correct 141 ms 7404 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 1016 KB Output is correct
2 Correct 42 ms 1272 KB Output is correct
3 Correct 88 ms 2548 KB Output is correct
4 Correct 84 ms 2420 KB Output is correct
5 Correct 112 ms 1916 KB Output is correct
6 Correct 133 ms 3692 KB Output is correct
7 Correct 140 ms 2808 KB Output is correct
8 Correct 117 ms 4708 KB Output is correct
9 Correct 610 ms 12508 KB Output is correct
10 Correct 366 ms 5240 KB Output is correct
11 Correct 402 ms 6648 KB Output is correct
12 Correct 580 ms 11244 KB Output is correct
13 Correct 500 ms 12396 KB Output is correct