Submission #958601

#	Time	Username	Problem	Language	Result	Execution time	Memory
958601		Ghetto	Cake (CEOI14_cake)	C++17	0 / 100	1392 ms	18884 KiB

cake

#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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50