oj.uz

Submission #958601

# Submission time Handle Problem Language Result Execution time Memory
958601 2024-04-06T06:30:11 Z Ghetto Cake (CEOI14_cake) C++17
0 / 100
 1392 ms 18884 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) {
        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++) {
        if (i == s) continue;
        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();

    // cout << "HELLO" << endl;
    // for (pii el : vals) cout << el.second << "," << el.first << "  ";
    // cout << endl;
    // for (int el : ls) cout << el << " ";
    // cout << endl;
    // for (int el : rs) cout << el << " ";
    // cout << endl;
    // cout << "HELLO" << endl;

    for (int i = 1; i <= q; i++) {
        char ch; cin >> ch;
        if (ch == 'E') {
            int i, p; cin >> i >> p;
            if (i == s) continue;
            update1(i, p);

            // cout << "HELLO" << endl;
            // for (pii el : vals) cout << el.second << "," << el.first << "  ";
            // cout << endl;
            // for (int el : ls) cout << el << " ";
            // cout << endl;
            // for (int el : rs) cout << el << " ";
            // cout << endl;
            // cout << "HELLO" << endl;
        } else {
            int i; cin >> i;
            cout << query(i) << '\n';
        }  
    }
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Incorrect 10 ms 2392 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 657 ms 2908 KB Output is correct
2 Incorrect 392 ms 2908 KB Output isn't correct
3 Correct 493 ms 3072 KB Output is correct
4 Correct 296 ms 2904 KB Output is correct
5 Incorrect 823 ms 5860 KB Output isn't correct
6 Incorrect 624 ms 5876 KB Output isn't correct
7 Correct 538 ms 5720 KB Output is correct
8 Correct 339 ms 5720 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 9796 KB Output is correct
2 Incorrect 193 ms 9808 KB Output isn't correct
3 Incorrect 190 ms 9776 KB Output isn't correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 320 ms 17568 KB Output is correct
6 Correct 322 ms 17636 KB Output is correct
7 Incorrect 268 ms 17488 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 88 ms 2728 KB Output isn't correct
2 Incorrect 86 ms 2848 KB Output isn't correct
3 Incorrect 176 ms 7312 KB Output isn't correct
4 Correct 169 ms 7208 KB Output is correct
5 Incorrect 259 ms 2900 KB Output isn't correct
6 Correct 285 ms 8108 KB Output is correct
7 Correct 279 ms 3412 KB Output is correct
8 Correct 323 ms 9456 KB Output is correct
9 Correct 1392 ms 18560 KB Output is correct
10 Incorrect 854 ms 3576 KB Output isn't correct
11 Correct 959 ms 6780 KB Output is correct
12 Correct 1311 ms 16108 KB Output is correct
13 Correct 1138 ms 18884 KB Output is correct