oj.uz

답안 #958598

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
958598 2024-04-06T06:00:02 Z Ghetto 케이크 (CEOI14_cake) C++17
0 / 100
 1200 ms 14676 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;
    if (s == 1) return 0;
    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;
    if (s == n) return n + 1;
    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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 581 ms 860 KB Output is correct
2 Incorrect 347 ms 932 KB Output isn't correct
3 Correct 435 ms 860 KB Output is correct
4 Correct 251 ms 860 KB Output is correct
5 Correct 638 ms 1692 KB Output is correct
6 Incorrect 553 ms 1696 KB Output isn't correct
7 Correct 476 ms 1628 KB Output is correct
8 Correct 292 ms 1628 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 213 ms 5940 KB Output is correct
2 Incorrect 189 ms 5972 KB Output isn't correct
3 Incorrect 190 ms 5860 KB Output isn't correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 317 ms 13652 KB Output is correct
6 Correct 299 ms 13760 KB Output is correct
7 Incorrect 259 ms 13396 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 90 ms 800 KB Output isn't correct
2 Incorrect 72 ms 604 KB Output isn't correct
3 Incorrect 143 ms 3156 KB Output isn't correct
4 Correct 163 ms 3408 KB Output is correct
5 Incorrect 248 ms 828 KB Output isn't correct
6 Incorrect 247 ms 4172 KB Output isn't correct
7 Incorrect 301 ms 1316 KB Output isn't correct
8 Correct 251 ms 5456 KB Output is correct
9 Incorrect 1189 ms 14676 KB Output isn't correct
10 Incorrect 834 ms 1632 KB Output isn't correct
11 Incorrect 880 ms 2800 KB Output isn't correct
12 Correct 1200 ms 12116 KB Output is correct
13 Correct 1034 ms 14656 KB Output is correct