Submission #47465

#	Time	Username	Problem	Language	Result	Execution time	Memory
47465		TAMREF	Cake (CEOI14_cake)	C++11	0 / 100	1371 ms	17292 KiB

cake

#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){

    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, l));
    }else if(l < a){
        return bs_MAX(I.RMQ(l, a)) - 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: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50