oj.uz

Submission #47465

# Submission time Handle Problem Language Result Execution time Memory
47465 2018-05-03T10:12:03 Z TAMREF Cake (CEOI14_cake) C++11
0 / 100
 1371 ms 17292 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){

    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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Incorrect 4 ms 2496 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 569 ms 2992 KB Output is correct
2 Incorrect 290 ms 3156 KB Output isn't correct
3 Correct 381 ms 3212 KB Output is correct
4 Correct 218 ms 3212 KB Output is correct
5 Correct 679 ms 3964 KB Output is correct
6 Incorrect 544 ms 3964 KB Output isn't correct
7 Correct 447 ms 4004 KB Output is correct
8 Correct 242 ms 4004 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 8228 KB Output is correct
2 Incorrect 116 ms 8288 KB Output isn't correct
3 Incorrect 112 ms 8304 KB Output isn't correct
4 Incorrect 4 ms 8304 KB Output isn't correct
5 Correct 293 ms 16084 KB Output is correct
6 Correct 313 ms 16128 KB Output is correct
7 Incorrect 177 ms 16272 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 16272 KB Output isn't correct
2 Incorrect 43 ms 16272 KB Output isn't correct
3 Incorrect 131 ms 16272 KB Output isn't correct
4 Incorrect 146 ms 16272 KB Output isn't correct
5 Incorrect 164 ms 16272 KB Output isn't correct
6 Incorrect 229 ms 16272 KB Output isn't correct
7 Incorrect 170 ms 16272 KB Output isn't correct
8 Correct 287 ms 16272 KB Output is correct
9 Incorrect 1371 ms 17292 KB Output isn't correct
10 Incorrect 493 ms 17292 KB Output isn't correct
11 Incorrect 793 ms 17292 KB Output isn't correct
12 Correct 1314 ms 17292 KB Output is correct
13 Correct 960 ms 17292 KB Output is correct