oj.uz

Submission #375619

# Submission time Handle Problem Language Result Execution time Memory
375619 2021-03-09T15:36:42 Z dolphingarlic Cake (CEOI14_cake) C++14
100 / 100
 598 ms 13672 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int d[250001], segtree[2][1000001];

void update(int *seg, int pos, int val, int node, int l, int r) {
    if (l == r) seg[node] = val;
    else {
        int mid = (l + r) / 2;
        if (pos > mid) update(seg, pos, val, node * 2 + 1, mid + 1, r);
        else update(seg, pos, val, node * 2, l, mid);
        seg[node] = max(seg[node * 2], seg[node * 2 + 1]);
    }
}

int range_max(int *seg, int a, int b, int node, int l, int r) {
    if (l > b || r < a) return 0;
    if (l >= a && r <= b) return seg[node];
    int mid = (l + r) / 2;
    return max(range_max(seg, a, b, node * 2, l, mid), range_max(seg, a, b, node * 2 + 1, mid + 1, r));
}

int walk(int *seg, int threshold, int node, int l, int r) {
    if (threshold > seg[node]) return r;
    if (l == r) return l - (seg[node] > threshold);
    int mid = (l + r) / 2;
    if (seg[node * 2] >= threshold) return walk(seg, threshold, node * 2, l, mid);
    return walk(seg, threshold, node * 2 + 1, mid + 1, r);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, a;
    cin >> n >> a;
    vector<int> top_ten;
    for (int i = 1; i <= n; i++) {
        cin >> d[i];
        top_ten.push_back(i);
    }
    sort(top_ten.begin(), top_ten.end(), [](int A, int B) { return d[A] > d[B]; });
    while (top_ten.size() > 10) top_ten.pop_back();

    for (int i = a + 1; i <= n; i++) update(segtree[0], i - a, d[i], 1, 1, n - a);
    for (int i = a - 1; i; i--) update(segtree[1], a - i, d[i], 1, 1, a - 1);

    int q;
    cin >> q;
    while (q--) {
        char c;
        cin >> c;
        if (c == 'F') {
            int b;
            cin >> b;
            if (b == a) cout << "0\n";
            else if (b > a) {
                int mx = range_max(segtree[0], 1, b - a, 1, 1, n - a);
                cout << walk(segtree[1], mx, 1, 1, a - 1) + b - a << '\n';
            } else {
                int mx = range_max(segtree[1], 1, a - b, 1, 1, a - 1);
                cout << walk(segtree[0], mx, 1, 1, n - a) + a - b << '\n';
            }
        } else {
            int i, e;
            cin >> i >> e;

            auto it = find(top_ten.begin(), top_ten.end(), i);
            if (it != top_ten.end()) top_ten.erase(it);
            
            for (int i = 0; i < e - 1; i++) {
                d[top_ten[i]]++;
                if (top_ten[i] > a)
                    update(segtree[0], top_ten[i] - a, d[top_ten[i]], 1, 1, n - a);
                else if (top_ten[i] < a)
                    update(segtree[1], a - top_ten[i], d[top_ten[i]], 1, 1, a - 1);
            }

            d[i] = d[top_ten[e - 1]] + 1;
            if (i > a) update(segtree[0], i - a, d[i], 1, 1, n - a);
            else if (i < a) update(segtree[1], a - i, d[i], 1, 1, a - 1);

            top_ten.insert(top_ten.begin() + e - 1, i);
            if (top_ten.size() > 10) top_ten.pop_back();
        }
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 4 ms 492 KB Output is correct
5 Correct 11 ms 876 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 5100 KB Output is correct
2 Correct 150 ms 5100 KB Output is correct
3 Correct 206 ms 5100 KB Output is correct
4 Correct 145 ms 5100 KB Output is correct
5 Correct 318 ms 5740 KB Output is correct
6 Correct 256 ms 6124 KB Output is correct
7 Correct 240 ms 5864 KB Output is correct
8 Correct 163 ms 5996 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 4328 KB Output is correct
2 Correct 79 ms 4204 KB Output is correct
3 Correct 76 ms 4068 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 148 ms 7656 KB Output is correct
6 Correct 144 ms 7572 KB Output is correct
7 Correct 125 ms 7524 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1004 KB Output is correct
2 Correct 24 ms 1004 KB Output is correct
3 Correct 61 ms 2544 KB Output is correct
4 Correct 76 ms 2544 KB Output is correct
5 Correct 85 ms 1900 KB Output is correct
6 Correct 117 ms 3948 KB Output is correct
7 Correct 94 ms 2796 KB Output is correct
8 Correct 143 ms 4928 KB Output is correct
9 Correct 598 ms 12540 KB Output is correct
10 Correct 288 ms 5228 KB Output is correct
11 Correct 388 ms 6636 KB Output is correct
12 Correct 577 ms 11624 KB Output is correct
13 Correct 469 ms 13672 KB Output is correct