oj.uz

Submission #958604

# Submission time Handle Problem Language Result Execution time Memory
958604 2024-04-06T06:34:46 Z Ghetto Cake (CEOI14_cake) C++17
100 / 100
 1228 ms 14672 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) return;
    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++) { 
        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);
        } else {
            int i; cin >> i;
            cout << query(i) << '\n';
        }  
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 9 ms 348 KB Output is correct
5 Correct 22 ms 860 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 860 KB Output is correct
2 Correct 324 ms 856 KB Output is correct
3 Correct 446 ms 932 KB Output is correct
4 Correct 260 ms 856 KB Output is correct
5 Correct 667 ms 1624 KB Output is correct
6 Correct 507 ms 1624 KB Output is correct
7 Correct 480 ms 1624 KB Output is correct
8 Correct 288 ms 1628 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 5952 KB Output is correct
2 Correct 210 ms 5968 KB Output is correct
3 Correct 206 ms 5800 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 311 ms 13652 KB Output is correct
6 Correct 332 ms 13740 KB Output is correct
7 Correct 249 ms 13392 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 604 KB Output is correct
2 Correct 71 ms 600 KB Output is correct
3 Correct 138 ms 2980 KB Output is correct
4 Correct 158 ms 3132 KB Output is correct
5 Correct 243 ms 852 KB Output is correct
6 Correct 251 ms 4140 KB Output is correct
7 Correct 272 ms 1404 KB Output is correct
8 Correct 264 ms 5520 KB Output is correct
9 Correct 1211 ms 14672 KB Output is correct
10 Correct 816 ms 1596 KB Output is correct
11 Correct 890 ms 3040 KB Output is correct
12 Correct 1228 ms 12108 KB Output is correct
13 Correct 1066 ms 14672 KB Output is correct