답안 #96943 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96943	2019-02-12T19:53:48 Z	dalgerok	Growing Trees (BOI11_grow)	C++14	100 / 100	259 ms	7624 KB

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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	Grader output
1	Correct	259 ms	7624 KB	Output is correct

답안 #96943

Compilation message