Pagini recente » Cod sursa (job #1352946) | Cod sursa (job #1690038) | Cod sursa (job #2800433) | Cod sursa (job #347025) | Cod sursa (job #1660074)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 30010;
inline int Random() {
//return (rand() << 16) ^ rand();
return rand();
}
struct Node {
short key, priority, size;
Node *left, *right;
Node() {
}
Node(short key, short priority, short 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, short 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);
printf("%d\n", node->key);
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;
scanf("%d", &N);
for (i = 1; i <= N; ++i)
nodes[i] = new Node(i, Random(), 1, nil, nil);
for (i = 1; i <= N; ++i) {
scanf("%d", &pos);
auto split = Split(T, pos - 1);
T = Union(split.first, nodes[i]);
T = Union(T, split.second);
}
Print(T);
return 0;
}