Submission #86959

#	Time	Username	Problem	Language	Result	Execution time	Memory
86959		popovicirobert	Growing Trees (BOI11_grow)	C++14	100 / 100	227 ms	42704 KiB

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 / 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