Cod sursa(job #1660069)

Utilizator RazvanR104Razvan-Andrei Ciocoiu RazvanR104 Data 22 martie 2016 19:39:33
Problema Schi Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 30010;

inline int Random() {
    return (rand() << 16) ^ rand();
}

struct Node {
    int key, priority, size;
    Node *left, *right;

    Node() {
    }
    Node(int key, int priority, int size, Node *left, Node *right):
        key(key),
        priority(priority),
        size(size),
        left(left),
        right(right) {
    }
} *T, *nil, *nodes[NMAX];

int N;

void Update(Node *node) {
    if (node == nil)
        return;
    node->size = 1 + node->left->size + node->right->size;
}

pair<Node *, Node *> Split(Node *node, int pos) {
    if (node == nil)
        return {nil, nil};

    if (pos <= node->left->size) {
        auto split = Split(node->left, pos);
        node->left = split.second;
        split.second = node;
        Update(node);
        return split;
    } else {
        auto split = Split(node->right, pos - 1 - node->left->size);
        node->right = split.first;
        split.first = node;
        Update(node);
        return split;
    }
}

Node *Union(Node *left, Node *right) {
    if (left == nil)
        return right;
    if (right == nil)
        return left;

    if (left->priority >= right->priority) {
        left->right = Union(left->right, right);
        Update(left);
        return left;
    } else {
        right->left = Union(left, right->left);
        Update(right);
        return right;
    }
}

void Print(Node *node) {
    if (node == nil)
        return;
    Print(node->left);
    cout << node->key << '\n';
    Print(node->right);
}

int main() {
    assert(freopen("schi.in", "r", stdin));
    assert(freopen("schi.out", "w", stdout));

    srand(time(0));

    T = nil = new Node(-1, -1, 0, 0, 0);
    nil->left = nil->right = nil;

    int i, j, pos;
    cin >> N;

    for (i = 1; i <= N; ++i)
        nodes[i] = new Node(i, Random(), 1, nil, nil);

    for (i = 1; i <= N; ++i) {
        cin >> pos;
        auto split = Split(T, pos - 1);
        T = Union(split.first, nodes[i]);
        T = Union(T, split.second);
    }
    Print(T);

    return 0;
}