oj.uz

Submission #958602

# Submission time Handle Problem Language Result Execution time Memory
958602 2024-04-06T06:33:11 Z Ghetto Cake (CEOI14_cake) C++17
100 / 100
 1431 ms 18796 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAX_N = 250000 + 5;

int n, s;
int val[MAX_N];
int q;

set<pii> vals; // {val, ind}
set<int> ls, rs;

int segtree[4 * MAX_N];
void update(int i, int x, int u = 1, int lo = 1, int hi = n) {
    if (lo == hi) {
        segtree[u] = x;
        return;
    }

    int mid = (lo + hi) / 2;
    if (i <= mid) update(i, x, 2 * u, lo, mid);
    else update(i, x, 2 * u + 1, mid + 1, hi);
    segtree[u] = max(segtree[2 * u], segtree[2 * u + 1]);
}
int r_walk(int l, int r, int x, int u = 1, int lo = 1, int hi = n) { // First el. in [l, r] s.t. val[i] > x (r + 1 otherwise)
    if (l > r) return r + 1;
    if (hi < l || r < lo) return r + 1;
    if (segtree[u] <= x) return r + 1;
    
    if (lo == hi) return lo;

    int mid = (lo + hi) / 2;
    int resp = r_walk(l, r, x, 2 * u, lo, mid);
    if (resp != r + 1) return resp;    
    return r_walk(l, r, x, 2 * u + 1, mid + 1, hi);
}
int l_walk(int l, int r, int x, int u = 1, int lo = 1, int hi = n) {
    if (l > r) return l - 1;
    if (hi < l || r < lo) return l - 1;
    if (segtree[u] <= x) return l - 1;

    if (lo == hi) return lo;

    int mid = (lo + hi) / 2;
    int resp = l_walk(l, r, x, 2 * u + 1, mid + 1, hi);
    if (resp != l - 1) return resp; 
    return l_walk(l, r, x, 2 * u, lo, mid);
}

void update2(int i, int new_val) {
    val[i] = new_val;
    update(i, val[i]); 

    if (i == s) return;
    if (i < s) {
        if (ls.count(i)) ls.erase(i);

        auto it = ls.upper_bound(i);
        if (it != ls.end() && val[*it] > val[i]) return;

        while (ls.upper_bound(i) != ls.begin() && val[*next(ls.upper_bound(i), -1)] < val[i])
            ls.erase(next(ls.upper_bound(i), -1));
        ls.insert(i);
    } else {
        if (rs.count(i)) rs.erase(i);

        auto it = rs.upper_bound(i);
        if (it != rs.begin() && val[*next(it, -1)] > val[i]) return;

        while (rs.upper_bound(i) != rs.end() && val[*rs.upper_bound(i)] < val[i])
            rs.erase(rs.upper_bound(i));
        rs.insert(i);
    }
}
void update1(int i, int p) {
    vector<int> to_erase; // Highest to lowest position
    auto it = vals.end();
    for (int j = 1; j <= p; j++) {
        it--;
        if (j != p) to_erase.push_back(it->second);
    }
    int new_val = it->first + 1;

    vals.erase({val[i], i});
    vals.insert({new_val, i});
    for (int el : to_erase) {
        vals.erase({val[el], el});
        vals.insert({val[el] + 1, el});
    }

    for (int el : to_erase) update2(el, val[el] + 1);
    update2(i, new_val);
}

int query(int i) {
    if (i == s) return 0;
    if (i < s) {
        int j = *ls.lower_bound(i);
        int k = r_walk(s + 1, n, val[j]);
        return k - 1 - (i + 1) + 1;
    } else {
        int j = *next(rs.upper_bound(i), -1);
        int k = l_walk(1, s - 1, val[j]);
        return i - 1 - (k + 1) + 1;
    }
}

void init() {
    for (int i = 1; i <= n; i++) {
        vals.insert({val[i], i});
        update2(i, val[i]);
    }
}

int main() {
    // freopen("cake.in", "r", stdin);
    // freopen("cake.out", "w", stdout);

    cin >> n >> s;
    for (int i = 1; i <= n; i++) cin >> val[i];
    cin >> q;

    init();

    for (int i = 1; i <= q; i++) {
        char ch; cin >> ch;
        if (ch == 'E') {
            int i, p; cin >> i >> p;
            update1(i, p);
        } else {
            int i; cin >> i;
            cout << query(i) << '\n';
        }  
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 9 ms 2648 KB Output is correct
5 Correct 24 ms 3240 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 701 ms 2908 KB Output is correct
2 Correct 382 ms 2908 KB Output is correct
3 Correct 490 ms 3072 KB Output is correct
4 Correct 272 ms 2904 KB Output is correct
5 Correct 743 ms 5816 KB Output is correct
6 Correct 604 ms 5720 KB Output is correct
7 Correct 564 ms 5724 KB Output is correct
8 Correct 325 ms 5724 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 9948 KB Output is correct
2 Correct 191 ms 9836 KB Output is correct
3 Correct 193 ms 9712 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 329 ms 18004 KB Output is correct
6 Correct 328 ms 17544 KB Output is correct
7 Correct 277 ms 17684 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 2684 KB Output is correct
2 Correct 72 ms 2872 KB Output is correct
3 Correct 146 ms 7104 KB Output is correct
4 Correct 175 ms 7136 KB Output is correct
5 Correct 265 ms 2836 KB Output is correct
6 Correct 282 ms 8036 KB Output is correct
7 Correct 282 ms 3412 KB Output is correct
8 Correct 326 ms 9300 KB Output is correct
9 Correct 1431 ms 18796 KB Output is correct
10 Correct 869 ms 3640 KB Output is correct
11 Correct 970 ms 7160 KB Output is correct
12 Correct 1351 ms 16152 KB Output is correct
13 Correct 1130 ms 18512 KB Output is correct