oj.uz

Submission #958597

# Submission time Handle Problem Language Result Execution time Memory
958597 2024-04-06T05:44:36 Z Ghetto Cake (CEOI14_cake) C++17
0 / 100
 1173 ms 21160 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;

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 5224 KB Output is correct
2 Incorrect 357 ms 5284 KB Output isn't correct
3 Correct 430 ms 5276 KB Output is correct
4 Correct 259 ms 5272 KB Output is correct
5 Correct 645 ms 6280 KB Output is correct
6 Incorrect 534 ms 6552 KB Output isn't correct
7 Correct 463 ms 6476 KB Output is correct
8 Correct 303 ms 6672 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 7284 KB Output is correct
2 Incorrect 192 ms 7248 KB Output isn't correct
3 Incorrect 193 ms 7296 KB Output isn't correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 313 ms 16312 KB Output is correct
6 Correct 308 ms 16212 KB Output is correct
7 Incorrect 260 ms 16440 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 83 ms 856 KB Output isn't correct
2 Incorrect 71 ms 1164 KB Output isn't correct
3 Incorrect 142 ms 3968 KB Output isn't correct
4 Correct 162 ms 3964 KB Output is correct
5 Incorrect 240 ms 1948 KB Output isn't correct
6 Incorrect 244 ms 5716 KB Output isn't correct
7 Incorrect 275 ms 2860 KB Output isn't correct
8 Correct 247 ms 7844 KB Output is correct
9 Incorrect 1173 ms 21160 KB Output isn't correct
10 Incorrect 809 ms 5116 KB Output isn't correct
11 Incorrect 905 ms 7128 KB Output isn't correct
12 Correct 1163 ms 18016 KB Output is correct
13 Correct 1014 ms 21032 KB Output is correct