oj.uz

Submission #47467

# Submission time Handle Problem Language Result Execution time Memory
47467 2018-05-03T10:24:53 Z TAMREF Cake (CEOI14_cake) C++11
100 / 100
 1382 ms 17432 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; ///n, a modifying. k, l should NOT be incremented
    cin >> q;

    I.init(n+1, d);
    for(int i = 1; i < n; i++){
        //printf("d[%d] = %d\n",i,d[i]);
        S.emplace(d[i],i);
    }
}

void enhance(int k, int e){

    //printf("enhance(%d, %d)\n",k,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]);
    }

    //printf("nv = %d\n", nv);
    S.erase({d[k], k});
    S.emplace(d[k] = nv, k);
    I.upd(k, d[k]);

    //for(int i = 0; i <= n; i++) printf("%d ",d[i]); puts("");
    //for(int i = 0; i <= n; i++) printf("%d ",I.a[o+i]); puts("");
}

int bs_min(int X){
    //printf("bs_min(%d)\n",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){
    //printf("bs_MAX(%d)\n",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;
        //printf("lo = %d, mi = %d, hi = %d, RMQ = %d\n",lo,mi,hi,I.RMQ(a+1,mi));
        if(I.RMQ(a+1, mi) > X) hi = mi - 1;
        else lo = mi;
    }
    //printf("lo = %d\n",lo);
    return lo;
}

int numCake(int l){
    //printf("numCake(%d, %d)\n",l,a);
    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;
        ////printf("c = %c\n",c);
        if(c == 'E'){
            cin >> u >> v;
            enhance(u, v);
        }else if(c == 'F'){
            cin >> u;
            cout << numCake(u) << '\n';
        }else{
            assert(0);
        }
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 4 ms 2424 KB Output is correct
3 Correct 4 ms 2604 KB Output is correct
4 Correct 9 ms 2716 KB Output is correct
5 Correct 18 ms 3444 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 574 ms 3444 KB Output is correct
2 Correct 364 ms 3552 KB Output is correct
3 Correct 378 ms 3552 KB Output is correct
4 Correct 204 ms 3552 KB Output is correct
5 Correct 749 ms 4196 KB Output is correct
6 Correct 579 ms 4336 KB Output is correct
7 Correct 430 ms 4336 KB Output is correct
8 Correct 304 ms 4336 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 8560 KB Output is correct
2 Correct 118 ms 8560 KB Output is correct
3 Correct 86 ms 8560 KB Output is correct
4 Correct 4 ms 8560 KB Output is correct
5 Correct 355 ms 16252 KB Output is correct
6 Correct 428 ms 16368 KB Output is correct
7 Correct 152 ms 16368 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 16368 KB Output is correct
2 Correct 108 ms 16368 KB Output is correct
3 Correct 138 ms 16368 KB Output is correct
4 Correct 188 ms 16368 KB Output is correct
5 Correct 219 ms 16368 KB Output is correct
6 Correct 273 ms 16368 KB Output is correct
7 Correct 213 ms 16368 KB Output is correct
8 Correct 292 ms 16368 KB Output is correct
9 Correct 1382 ms 17432 KB Output is correct
10 Correct 520 ms 17432 KB Output is correct
11 Correct 764 ms 17432 KB Output is correct
12 Correct 1324 ms 17432 KB Output is correct
13 Correct 1044 ms 17432 KB Output is correct