oj.uz

Submission #47468

# Submission time Handle Problem Language Result Execution time Memory
47468 2018-05-03T10:26:41 Z TAMREF Cake (CEOI14_cake) C++11
100 / 100
 1381 ms 17272 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;
    cin >> q;

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

void enhance(int k, int 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]);
    }

    S.erase({d[k], k});
    S.emplace(d[k] = nv, k);
    I.upd(k, d[k]);
}

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){
    if(I.a[o + a + 1] > X) return a;
    int lo = a + 1, mi, hi = n;
    while(lo < hi){
        mi = (lo + hi + 1) >> 1;
        if(I.RMQ(a+1, mi) > X) hi = mi - 1;
        else lo = mi;
    }
    return lo;
}

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2296 KB Output is correct
2 Correct 4 ms 2404 KB Output is correct
3 Correct 4 ms 2480 KB Output is correct
4 Correct 8 ms 2516 KB Output is correct
5 Correct 19 ms 3028 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 3028 KB Output is correct
2 Correct 366 ms 3052 KB Output is correct
3 Correct 397 ms 3172 KB Output is correct
4 Correct 186 ms 3172 KB Output is correct
5 Correct 658 ms 3968 KB Output is correct
6 Correct 610 ms 3992 KB Output is correct
7 Correct 493 ms 3992 KB Output is correct
8 Correct 268 ms 3992 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 8188 KB Output is correct
2 Correct 92 ms 8244 KB Output is correct
3 Correct 107 ms 8244 KB Output is correct
4 Correct 4 ms 8244 KB Output is correct
5 Correct 324 ms 16040 KB Output is correct
6 Correct 280 ms 16212 KB Output is correct
7 Correct 188 ms 16212 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 16212 KB Output is correct
2 Correct 44 ms 16212 KB Output is correct
3 Correct 145 ms 16212 KB Output is correct
4 Correct 151 ms 16212 KB Output is correct
5 Correct 155 ms 16212 KB Output is correct
6 Correct 213 ms 16212 KB Output is correct
7 Correct 169 ms 16212 KB Output is correct
8 Correct 292 ms 16212 KB Output is correct
9 Correct 1381 ms 17272 KB Output is correct
10 Correct 517 ms 17272 KB Output is correct
11 Correct 743 ms 17272 KB Output is correct
12 Correct 1375 ms 17272 KB Output is correct
13 Correct 975 ms 17272 KB Output is correct