oj.uz

Submission #96943

# Submission time Handle Problem Language Result Execution time Memory
96943 2019-02-12T19:53:48 Z dalgerok Growing Trees (BOI11_grow) C++14
100 / 100
 259 ms 7624 KB 
#include<bits/stdc++.h>
using namespace std;


const int N = 1e5 + 5;




int n, m, a[N];


struct item{
    item *l, *r;
    int key, prior, mx, ob, cnt;
    item(){}
    item(int x){
        key = mx = x;
        ob = 0;
        cnt = 1;
        prior = (rand() ^ (rand() << 15));
        l = r = nullptr;
    }
};
typedef item *pitem;
pitem t;

inline int cnt(pitem v){
    return v ? v->cnt : 0;
}
inline int mx(pitem v){
    return v ? v->mx : 0;
}
inline void upd_cnt(pitem v){
    if(v){
        v->cnt = cnt(v->l) + 1 + cnt(v->r);
        v->mx = max({mx(v->l), v->key, mx(v->r)});
    }
}
inline void Push(pitem v){
    if(v && v->ob){
        if(v->l){
            v->l->ob += v->ob;
        }
        if(v->r){
            v->r->ob += v->ob;
        }
        v->key += v->ob;
        v->ob = 0;
    }
}
void Merge(pitem &v, pitem l, pitem r){
    Push(l);
    Push(r);
    if(!l || !r){
        v = l ? l : r;
        return;
    }
    if(l->prior > r->prior){
        Merge(l->r, l->r, r);
        v = l;
    }
    else{
        Merge(r->l, l, r->l);
        v = r;
    }
    upd_cnt(v);
}
void Split(pitem v, int key, pitem &l, pitem &r){
    Push(v);
    if(!v){
        l = r = nullptr;
        return;
    }
    if(key < v->key){
        Split(v->l, key, l, v->l);
        r = v;
    }
    else{
        Split(v->r, key, v->r, r);
        l = v;
    }
    upd_cnt(v);
}
void Split_cnt(pitem v, int key, pitem &l, pitem &r, int add = 0){
    Push(v);
    if(!v){
        l = r = nullptr;
        return;
    }
    int cur_key = cnt(v->l) + add;
    if(key <= cur_key){
        Split_cnt(v->l, key, l, v->l, add);
        r = v;
    }
    else{
        Split_cnt(v->r, key, v->r, r, add + 1 + cnt(v->l));
        l = v;
    }
    upd_cnt(v);
}


int main(){
    srand(time(nullptr));
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++){
        Merge(t, t, new item(a[i]));
    }
    while(m--){
        char type;
        cin >> type;
        if(type == 'F'){
            int c, h;
            cin >> c >> h;
            pitem tl, tr;
            Split(t, h - 1, tl, t);
            Split_cnt(t, min(cnt(t), c), t, tr);
            int val = mx(t);
            pitem tll, trr;
            Split(t, val - 1, tll, trr);
            if(tll){
                tll->ob += 1;
            }
            if(trr){
                trr->ob += 1;
            }
            pitem tlll, trrr;
            Split(tr, val, tlll, trrr);
            Merge(t, tl, tll);
            Merge(t, t, tlll);
            Merge(t, t, trr);
            Merge(t, t, trrr);
        }
        else{
            int l, r;
            cin >> l >> r;
            pitem tl, tr;
            Split(t, r, t, tr);
            Split(t, l - 1, tl, t);
            cout << cnt(t) << "\n";
            Merge(t, tl, t);
            Merge(t, t, tr);
        }
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 6396 KB Output is correct
2 Correct 198 ms 6520 KB Output is correct
3 Correct 102 ms 6392 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 408 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 86 ms 1772 KB Output is correct
6 Correct 101 ms 1964 KB Output is correct
7 Correct 10 ms 640 KB Output is correct
8 Correct 38 ms 1400 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 2072 KB Output is correct
2 Correct 110 ms 2280 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 50 ms 1760 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 2164 KB Output is correct
2 Correct 115 ms 2088 KB Output is correct
3 Correct 13 ms 896 KB Output is correct
4 Correct 101 ms 2168 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 4856 KB Output is correct
2 Correct 225 ms 5556 KB Output is correct
3 Correct 33 ms 1664 KB Output is correct
4 Correct 79 ms 5336 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 5312 KB Output is correct
2 Correct 229 ms 5756 KB Output is correct
3 Correct 98 ms 5624 KB Output is correct
4 Correct 36 ms 1684 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 5624 KB Output is correct
2 Correct 157 ms 6208 KB Output is correct
3 Correct 107 ms 6136 KB Output is correct
4 Correct 32 ms 1664 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 6620 KB Output is correct
2 Correct 197 ms 5624 KB Output is correct
3 Correct 69 ms 6264 KB Output is correct
4 Correct 93 ms 6136 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 6236 KB Output is correct
2 Correct 201 ms 6620 KB Output is correct
3 Correct 222 ms 7336 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 7624 KB Output is correct