Cod sursa(job #1806144)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 14 noiembrie 2016 21:05:45
Problema A+B Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
using ll = long long;

struct treap
{
    int key, pri, sum;
    treap *l, *r;

    treap(int _key = 0, treap *_l = nullptr, treap *_r = nullptr, int _pri = rand()) :
        key(_key), l(_l), r(_r), pri(_pri), sum(0) { }
};

void calc(treap *&root)
{
    if (!root) return;

    root->sum = root->key;
    if (root->l) root->sum += root->l->sum;
    if (root->r) root->sum += root->r->sum;
}

void merge(treap *&root, treap *&l, treap *&r)
{
    if (!l || !r) { root = (l ? l : r); return; }

    if (l->pri > r->pri) merge(l->r, l->r, r), root = l;
    else merge(r->l, l, r->l), root = r;

    calc(root);
}

void split(treap *root, int key, treap *&l, treap *&r)
{
    if (!root) { l = r = nullptr; return; }

    if (root->key <= key) split(root->r, key, root->r, r), calc(l = root);
    else split(root->l, key, l, root->l), calc(r = root);
}

void insert(treap *&root, int key)
{
    treap *aux = new treap(key), *l, *r;

    split(root, key, l, r);
    merge(l, l, aux);
    merge(root, l, r);
}

void erase(treap *&root, int key)
{
    treap *l, *r, *aux;

    split(root, key, l, r);
    split(l, key - 1, l, aux);
    merge(root, l, r);

    delete aux;
}

int kth(treap *root, int k)
{
    int suml = root->l ? root->l->sum : 0;

    if (suml >= k) return kth(root->l, k);
    if (suml + 1 == k) return root->key;
    return kth(root->r, k - suml - 1);
}

int main()
{
    freopen("adunare.in", "r", stdin);
    freopen("adunare.out", "w", stdout);
    srand(69);

    int a, b;
    treap *root = nullptr;

    cin >> a >> b;

    insert(root, a);
    insert(root, b);

    cout << root->sum << '\n';

    return 0;
}