제출 #958597

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
958597		Ghetto	케이크 (CEOI14_cake)	C++17	0 / 100	1173 ms	21160 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;

void update2(int i, int new_val) {
    val[i] = new_val;
    
    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 l_bin_search(int x) {
    int lo = 1, hi = s - 1;
    while (lo != hi) {
        int mid = ceil((lo + hi) / (double) 2);

        auto it = ls.lower_bound(mid);
        if (val[*it] > x) lo = mid;
        else hi = mid - 1;
    }

    auto it = ls.lower_bound(lo);
    return (val[*it] > x) ? lo : 0;
}
int r_bin_search(int x) { // First index in [s + 1, n] with el. in rs <= it whose val > x
    int lo = s + 1, hi = n;
    while (lo != hi) {
        int mid = (lo + hi) / 2;
        
        auto it = rs.upper_bound(mid);
        assert(it != rs.begin());
        it--;

        if (val[*it] > x) hi = mid;
        else lo = mid + 1;
    }
    
    auto it = next(rs.upper_bound(lo), -1);
    return (val[*it] > x) ? lo : n + 1;
}

int query(int i) {
    if (i == s) return 0;
    if (i < s) {
        int j = *ls.lower_bound(i);
        int k = r_bin_search(val[j]);
        return k - 1 - (i + 1) + 1;
    } else {
        int j = *next(rs.upper_bound(i), -1);
        int k = l_bin_search(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]);
    }

    // for (int el : ls) cout << el << " ";
    // cout << endl;
    // for (int el : rs) cout << el << " ";
    // cout << endl;
}

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