Submission #96943

#	Time	Username	Problem	Language	Result	Execution time	Memory
96943		dalgerok	Growing Trees (BOI11_grow)	C++14	100 / 100	259 ms	7624 KiB

grow

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10