Cod sursa(job #1291217)

Utilizator dariusdariusMarian Darius dariusdarius Data 12 decembrie 2014 15:35:48
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <cstdlib>
#include <cstdio>

struct Treap {
    short value, dp, priority;
    Treap *left, *right;
    Treap() {}
    Treap(short vvalue, short ddp, short ppriority, Treap* lleft, Treap *rright) {
        value = vvalue;
        dp = ddp;
        priority = ppriority;
        left = lleft; right = rright;
    }
} *root, *NIL;

void dfs(const Treap* node) {
    if (node->left != NIL) {
        dfs(node->left);
    }
    printf("%d\n", node->value);
    if (node->right != NIL) {
        dfs(node->right);
    }
}

void rotate_left(Treap* &node) {
    Treap *x = node->left->left, *y = node->left->right, *z = node->right, *a = node, *b = node->left;
    node = b;
    node->left = x;
    node->right = a;
    node->right->left = y;
    node->right->right = z;
    node->right->dp = y->dp + z->dp + 1;
    node->dp = node->left->dp + node->right->dp + 1;
}

void rotate_right(Treap* &node) {
    Treap *x = node->left, *y = node->right->left, *z = node->right->right, *b = node, *a = node->right;
    node = a;
    node->left = b;
    node->right = z;
    node->left->left = x;
    node->left->right = y;
    node->left->dp = x->dp + y->dp + 1;
    node->dp = node->left->dp + node->right->dp + 1;
}

void balance(Treap* &node) {
    if (node->left->priority > node->priority) {
        rotate_left(node);
    } else if (node->right->priority > node->priority) {
        rotate_right(node);
    }
    node->dp = node->left->dp + node->right->dp + 1;
}

void insert(Treap* &node, short value, short key, short priority) {
    if (node == NIL) {
        node = new Treap(value, 1, priority, NIL, NIL);
        return;
    }
    if (node->left->dp >= key) {
        insert(node->left, value, key, priority);
    } else {
        insert(node->right, value, key - node->left->dp - 1, priority);
    }
    balance(node);
}

int main() {
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);
    int n; short x;
    scanf("%d%hd", &n, &x);
    NIL = new Treap(0, 0, 0, NULL, NULL);
    root = new Treap(1, 1, rand() % 32000 + 1, NIL, NIL);
    for (short i = 2; i <= n; ++ i) {
        scanf("%hd", &x);
        insert(root, i, x - 1, static_cast<short>(rand() % 32000 + 1));
    }
    dfs(root);
    return 0;
}