oj.uz

Submission #958600

# Submission time Handle Problem Language Result Execution time Memory
958600 2024-04-06T06:26:47 Z Ghetto Cake (CEOI14_cake) C++17
0 / 100
 1420 ms 18740 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();

    for (int i = 1; i <= q; i++) {
        char ch; cin >> ch;
        if (ch == 'E') {
            int i, p; cin >> i >> p;
            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 2 ms 2396 KB Output is correct
2 Incorrect 3 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 2908 KB Output is correct
2 Incorrect 395 ms 2904 KB Output isn't correct
3 Correct 502 ms 3072 KB Output is correct
4 Correct 270 ms 2908 KB Output is correct
5 Correct 751 ms 5868 KB Output is correct
6 Incorrect 648 ms 5848 KB Output isn't correct
7 Correct 532 ms 5720 KB Output is correct
8 Correct 307 ms 5720 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 9808 KB Output is correct
2 Incorrect 192 ms 10064 KB Output isn't correct
3 Incorrect 189 ms 9832 KB Output isn't correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 333 ms 17628 KB Output is correct
6 Correct 331 ms 17492 KB Output is correct
7 Incorrect 269 ms 17328 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 111 ms 2652 KB Output isn't correct
2 Incorrect 92 ms 2836 KB Output isn't correct
3 Incorrect 156 ms 7064 KB Output isn't correct
4 Correct 174 ms 7232 KB Output is correct
5 Incorrect 259 ms 2880 KB Output isn't correct
6 Incorrect 278 ms 8144 KB Output isn't correct
7 Incorrect 307 ms 3596 KB Output isn't correct
8 Correct 310 ms 9272 KB Output is correct
9 Incorrect 1375 ms 18740 KB Output isn't correct
10 Incorrect 865 ms 3608 KB Output isn't correct
11 Incorrect 975 ms 6948 KB Output isn't correct
12 Correct 1420 ms 16476 KB Output is correct
13 Correct 1152 ms 18668 KB Output is correct