oj.uz

Submission #47470

# Submission time Handle Problem Language Result Execution time Memory
47470 2018-05-03T10:44:04 Z TAMREF Cake (CEOI14_cake) C++11
100 / 100
 789 ms 17216 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
const int o = 262144, inf = 1e8;

struct Idxtree{
    int a[o+o];
    void init(int n, int *r){
        memset(a,0,sizeof(a));
        for(int i = 0; i < n; i++){
            a[o + i] = r[i];
        }
        for(int x = o; x > 1; x >>= 1){
            for(int y = x; y < x + x; y += 2){
                a[y >> 1] = max(a[y], a[y^1]);
            }
        }
    }
    int RMQ(int s, int e){
        s += o, e += o;
        int ret = max(a[s], a[e]);
        while(s <= e){
            ret = max({ret, a[s], a[e]});
            (++s) >>= 1;
            (--e) >>= 1;
        }
        return ret;
    }
    void upd(int i, int v){
        i += o;
        a[i] = v;
        while(i > 1){
            a[i >> 1] = max(a[i], a[i^1]);
            i >>=  1;
        }
    }
} I;

int d[o];
int n, a, q;
set<pii,greater<pii>> S;

void init(){
    cin >> n >> a;
    d[0] = d[n+1] = inf;
    for(int i = 1; i <= n; i++){
        cin >> d[i];
    }
    n += 1;
    cin >> q;

    I.init(n+1, d);
    for(int i = 1; i < n; i++){
        S.emplace(d[i],i);
    }
    while(S.size() > 10) S.erase(*S.rbegin());
}

void enhance(int k, int e){

    int nv = S.begin() -> first + 1;
    pii t[10];

    for(int i = 0; i < e - 1; i++){

        t[i] = *S.begin();
        S.erase(t[i]);

        nv = t[i].first;
    }
    for(int i = 0; i < e - 1; i++){
        S.emplace(d[t[i].second] = t[i].first + 1, t[i].second);
        I.upd(t[i].second, d[t[i].second]);
    }

    S.erase({d[k], k});
    S.emplace(d[k] = nv, k);
    I.upd(k, d[k]);
    
    while(S.size() > 10) S.erase(*S.rbegin());
}

int bs_min(int X){
    if(I.a[o + a - 1] > X) return a;
    int lo = 0, mi, hi = a - 1;

    while(lo < hi){
        mi = (lo + hi) >> 1;
        if(I.RMQ(mi, a-1) > X) lo = mi + 1;
        else hi = mi;
    }
    return hi;
}

int bs_MAX(int X){
    if(I.a[o + a + 1] > X) return a;
    int lo = a + 1, mi, hi = n;
    while(lo < hi){
        mi = (lo + hi + 1) >> 1;
        if(I.RMQ(a+1, mi) > X) hi = mi - 1;
        else lo = mi;
    }
    return lo;
}

int numCake(int l){
    if(l > a){
        return l - bs_min(I.RMQ(a+1, l));
    }else if(l < a){
        return bs_MAX(I.RMQ(l, a-1)) - l;
    }else{
        return 0;
    }
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    init();
    char c;
    for(int u, v, i = 0; i < q; i++){
        cin >> c;
        if(c == 'E'){
            cin >> u >> v;
            enhance(u, v);
        }else{
            cin >> u;
            cout << numCake(u) << '\n';
        }
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2428 KB Output is correct
2 Correct 4 ms 2536 KB Output is correct
3 Correct 4 ms 2616 KB Output is correct
4 Correct 8 ms 2620 KB Output is correct
5 Correct 15 ms 3196 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 3196 KB Output is correct
2 Correct 240 ms 3256 KB Output is correct
3 Correct 274 ms 3276 KB Output is correct
4 Correct 163 ms 3452 KB Output is correct
5 Correct 383 ms 3836 KB Output is correct
6 Correct 352 ms 3964 KB Output is correct
7 Correct 362 ms 4072 KB Output is correct
8 Correct 195 ms 4072 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 8324 KB Output is correct
2 Correct 110 ms 8324 KB Output is correct
3 Correct 92 ms 8324 KB Output is correct
4 Correct 4 ms 8324 KB Output is correct
5 Correct 348 ms 16164 KB Output is correct
6 Correct 340 ms 16164 KB Output is correct
7 Correct 166 ms 16164 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 16164 KB Output is correct
2 Correct 33 ms 16164 KB Output is correct
3 Correct 82 ms 16164 KB Output is correct
4 Correct 87 ms 16164 KB Output is correct
5 Correct 112 ms 16164 KB Output is correct
6 Correct 160 ms 16164 KB Output is correct
7 Correct 119 ms 16164 KB Output is correct
8 Correct 238 ms 16164 KB Output is correct
9 Correct 789 ms 17180 KB Output is correct
10 Correct 390 ms 17180 KB Output is correct
11 Correct 453 ms 17180 KB Output is correct
12 Correct 706 ms 17180 KB Output is correct
13 Correct 694 ms 17216 KB Output is correct