oj.uz

Submission #47462

# Submission time Handle Problem Language Result Execution time Memory
47462 2018-05-03T09:49:27 Z TAMREF Cake (CEOI14_cake) C++11
0 / 100
 1472 ms 17208 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;

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

        t = *S.begin();
        S.erase(t);

        S.emplace(d[t.second] = t.first + 1, t.second);
        I.upd(t.second, d[t.second]);

        nv = t.first;
    }

    //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)\n",l);
    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.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 510 ms 3044 KB Output isn't correct
2 Incorrect 303 ms 3096 KB Output isn't correct
3 Incorrect 455 ms 3096 KB Output isn't correct
4 Correct 238 ms 3276 KB Output is correct
5 Incorrect 641 ms 3992 KB Output isn't correct
6 Incorrect 494 ms 4052 KB Output isn't correct
7 Incorrect 389 ms 4076 KB Output isn't correct
8 Correct 237 ms 4076 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 158 ms 8316 KB Output isn't correct
2 Incorrect 176 ms 8332 KB Output isn't correct
3 Incorrect 114 ms 8524 KB Output isn't correct
4 Incorrect 4 ms 8524 KB Output isn't correct
5 Incorrect 304 ms 16108 KB Output isn't correct
6 Incorrect 299 ms 16152 KB Output isn't correct
7 Incorrect 194 ms 16180 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 16180 KB Output isn't correct
2 Incorrect 44 ms 16180 KB Output isn't correct
3 Incorrect 121 ms 16180 KB Output isn't correct
4 Incorrect 134 ms 16180 KB Output isn't correct
5 Incorrect 143 ms 16180 KB Output isn't correct
6 Incorrect 248 ms 16180 KB Output isn't correct
7 Incorrect 180 ms 16180 KB Output isn't correct
8 Incorrect 309 ms 16180 KB Output isn't correct
9 Incorrect 1340 ms 17208 KB Output isn't correct
10 Incorrect 416 ms 17208 KB Output isn't correct
11 Incorrect 764 ms 17208 KB Output isn't correct
12 Incorrect 1472 ms 17208 KB Output isn't correct
13 Incorrect 972 ms 17208 KB Output isn't correct