oj.uz

Submission #47461

# Submission time Handle Problem Language Result Execution time Memory
47461 2018-05-03T09:46:32 Z TAMREF Cake (CEOI14_cake) C++11
0 / 100
 1356 ms 102232 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){
    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;
    }
    if(hi < a - 1) return hi;
    return I.a[o + a - 1] > I.a[o + a] ? a : a-1;
}

int bs_MAX(int X){
    //printf("bs_MAX(%d)\n",X);
    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);
    if(lo > a + 1) return lo;
    return I.a[o + a + 1] > I.a[o + a] ? a : a + 1;
}

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;
        if(c == 'E'){
            cin >> u >> v;
            enhance(u, v);
        }else if(c == 'F'){
            cin >> u;
            cout << numCake(u) << '\n';
        }else{
            puts("QWAWEQRQWERWF");
        }
    }
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2424 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 480 ms 7540 KB Output isn't correct
2 Incorrect 296 ms 12068 KB Output isn't correct
3 Incorrect 381 ms 16416 KB Output isn't correct
4 Correct 241 ms 21068 KB Output is correct
5 Incorrect 642 ms 26268 KB Output isn't correct
6 Incorrect 613 ms 31396 KB Output isn't correct
7 Incorrect 498 ms 36368 KB Output isn't correct
8 Correct 256 ms 41388 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 146 ms 47064 KB Output isn't correct
2 Incorrect 118 ms 48320 KB Output isn't correct
3 Incorrect 108 ms 49780 KB Output isn't correct
4 Incorrect 5 ms 49780 KB Output isn't correct
5 Incorrect 369 ms 60188 KB Output isn't correct
6 Incorrect 328 ms 62440 KB Output isn't correct
7 Incorrect 211 ms 65008 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 65008 KB Output isn't correct
2 Incorrect 44 ms 65008 KB Output isn't correct
3 Incorrect 132 ms 65008 KB Output isn't correct
4 Incorrect 150 ms 65008 KB Output isn't correct
5 Incorrect 162 ms 65008 KB Output isn't correct
6 Incorrect 265 ms 65008 KB Output isn't correct
7 Incorrect 198 ms 65008 KB Output isn't correct
8 Incorrect 306 ms 66320 KB Output isn't correct
9 Incorrect 1343 ms 81916 KB Output isn't correct
10 Incorrect 439 ms 81916 KB Output isn't correct
11 Incorrect 674 ms 81916 KB Output isn't correct
12 Incorrect 1356 ms 93244 KB Output isn't correct
13 Incorrect 914 ms 102232 KB Output isn't correct