답안 #86959 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
86959	2018-11-28T20:18:23 Z	popovicirobert	Growing Trees (BOI11_grow)	C++14	100 / 100	227 ms	42704 KB

grow

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

typedef struct Treap *T;
typedef pair <T, T> PTT;

T NIL;

struct Treap {
    Treap *left, *right;
    int val, mx, lazy;
    int sz;
    int prio;
    Treap(int _val) {
        left = right = NIL;
        val = mx = _val;
        lazy = 0;
        sz = 1;
        prio = rand();
    }
};

T root = NIL;

inline void refresh(T nod) {
    nod -> sz = 1 + nod -> left -> sz + nod -> right -> sz;
    nod -> mx = max(nod -> val, max(nod -> left -> mx, nod -> right -> mx));
}

inline void solve_lazy(T nod) {
    nod -> left -> lazy += nod -> lazy;
    nod -> right -> lazy += nod -> lazy;
    nod -> val += nod -> lazy;
    nod -> lazy = 0;
}

T join(T a, T b) {
    if(a == NIL) {
        return b;
    }
    if(b == NIL) {
        return a;
    }
    solve_lazy(a);
    solve_lazy(b);
    if(a -> prio > b -> prio) {
        a -> right = join(a -> right, b);
        refresh(a);
        return a;
    }
    b -> left = join(a, b -> left);
    refresh(b);
    return b;
}

PTT split_val(T nod, int val) {
    if(nod == NIL) {
        return {NIL, NIL};
    }
    solve_lazy(nod);
    if(nod -> val > val) {
        PTT aux = split_val(nod -> left, val);
        nod -> left = aux.second;
        refresh(nod);
        return {aux.first, nod};
    }
    PTT aux = split_val(nod -> right, val);
    nod -> right = aux.first;
    refresh(nod);
    return {nod, aux.second};
}

PTT split_sz(T nod, int sz) {
    if(nod == NIL) {
        return {NIL, NIL};
    }
    solve_lazy(nod);
    if(nod -> left -> sz >= sz) {
        PTT aux = split_sz(nod -> left, sz);
        nod -> left = aux.second;
        refresh(nod);
        return {aux.first, nod};
    }
    PTT aux = split_sz(nod -> right, sz - nod -> left -> sz - 1);
    nod -> right = aux.first;
    refresh(nod);
    return {nod, aux.second};
}

/*void dfs(T nod) {
    if(nod == NIL) {
        return ;
    }
    solve_lazy(nod);
    dfs(nod -> left);
    cerr << nod -> val << " ";
    dfs(nod -> right);
    refresh(nod);
}*/

int main() {
    //ifstream cin("B.in");
    //ofstream cout("B.out");
    int i, n, m;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    NIL = new Treap(0);
    NIL -> left = NIL -> right = NIL;
    NIL -> sz = NIL -> prio = NIL -> val = NIL -> mx = NIL -> lazy = 0;
    root = NIL;
    cin >> n >> m;
    vector <int> arr;
    for(i = 1; i <= n; i++) {
        int h;
        cin >> h;
        arr.push_back(h);
    }
    sort(arr.begin(), arr.end());
    for(auto it : arr) {
        T aux = new Treap(it);
        root = join(root, aux);
    }
    while(m > 0) {
        m--;
        char ch;
        cin >> ch;
        if(ch == 'F') {
            int c, h;
            cin >> c >> h;
            PTT aux1 = split_val(root, h - 1);
            PTT aux2 = split_sz(aux1.second, min(aux1.second -> sz, c));
            //cerr << aux1.second -> sz << "\n";
            int val = aux2.first -> mx;
            PTT aux3 = split_val(aux2.first, val - 1);
            aux3.first -> lazy++;
            aux3.second -> lazy++;
            PTT aux4 = split_val(aux2.second, val);
            root = join(aux1.first, join(aux3.first, join(aux4.first, join(aux3.second, aux4.second))));
            //cerr << aux1.first -> sz << " " << aux2.first -> sz << " " << aux2.second -> sz << "\n";
        }
        else {
            int l, r;
            cin >> l >> r;
            PTT aux1 = split_val(root, r);
            PTT aux2 = split_val(aux1.first, l - 1);
            cout << aux2.second -> sz << "\n";
            root = join(join(aux2.first, aux2.second), aux1.second);
        }
        //dfs(root);
        //cerr << "\n";
    }
    //cin.close();
    //cout.close();
    return 0;
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	133 ms	6132 KB	Output is correct
2	Correct	184 ms	7676 KB	Output is correct
3	Correct	101 ms	9048 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	9048 KB	Output is correct
2	Correct	5 ms	9048 KB	Output is correct
3	Correct	6 ms	9048 KB	Output is correct
4	Correct	4 ms	9048 KB	Output is correct
5	Correct	84 ms	9048 KB	Output is correct
6	Correct	99 ms	9048 KB	Output is correct
7	Correct	8 ms	9048 KB	Output is correct
8	Correct	33 ms	9048 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	89 ms	9328 KB	Output is correct
2	Correct	97 ms	10268 KB	Output is correct
3	Correct	4 ms	10268 KB	Output is correct
4	Correct	48 ms	10968 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	69 ms	12172 KB	Output is correct
2	Correct	106 ms	13140 KB	Output is correct
3	Correct	17 ms	13140 KB	Output is correct
4	Correct	98 ms	14388 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	133 ms	18132 KB	Output is correct
2	Correct	196 ms	19720 KB	Output is correct
3	Correct	38 ms	19720 KB	Output is correct
4	Correct	90 ms	21188 KB	Output is correct

Subtask #6
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	175 ms	22632 KB	Output is correct
2	Correct	189 ms	24060 KB	Output is correct
3	Correct	93 ms	25152 KB	Output is correct
4	Correct	33 ms	25152 KB	Output is correct

Subtask #7
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	133 ms	27140 KB	Output is correct
2	Correct	149 ms	28736 KB	Output is correct
3	Correct	96 ms	29796 KB	Output is correct
4	Correct	33 ms	29796 KB	Output is correct

Subtask #8
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	191 ms	32200 KB	Output is correct
2	Correct	199 ms	32924 KB	Output is correct
3	Correct	58 ms	34628 KB	Output is correct
4	Correct	93 ms	35328 KB	Output is correct

Subtask #9
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	178 ms	36528 KB	Output is correct
2	Correct	187 ms	38208 KB	Output is correct
3	Correct	225 ms	40408 KB	Output is correct

Subtask #10
10.0 / 10.0

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

답안 #86959

Compilation message