Pagini recente » Cod sursa (job #2122055) | Cod sursa (job #2343608) | Cod sursa (job #931265) | Cod sursa (job #2941613) | Cod sursa (job #1847562)
#include <iostream>
#define in "schi.in"
#define out "schi.out"
struct tree {
tree *left;
tree *right;
int st;
int dr;
int position;
};
int rez[30001];
int maxim(int a, int b) {
return (a > b) ? a: b;
}
tree* updateTree(tree *node, int left, int right, int member, int pos) {
if ( node==NULL ) {
node = new tree;
node->left = NULL;
node->right = NULL;
node->st = left;
node->dr = right;
node->position = -1;
}
if (node->st==node->dr) {
if (node->dr == member) {
node->position = pos;
} else {
node->position++;
}
rez[node->position] = node->st;
return node;
}
int mid = (node->st+node->dr) / 2;
if (node->left != NULL && node->left->position >= pos || member <= mid) {
node->left = updateTree(node->left, node->st, mid, member, pos);
}
if (node->right != NULL && node->right->position >= pos || member > mid && member <= node->dr) {
node->right = updateTree(node->right, mid+1, node->dr, member, pos);
}
node->position = maxim(
(node->left != NULL) ? node->left->position : -1,
(node->right != NULL) ? node->right->position : -1
);
return node;
}
int main() {
freopen(in, "r", stdin);
freopen(out, "w", stdout);
int N;
scanf("%d", &N);
tree *root = NULL;
int pos;
for (int i=1; i<=N; i++) {
scanf("%d", &pos);
root = updateTree(root, 1, N, i, pos);
}
for (int i=1; i<=N; i++) {
printf("%d\n", rez[i]);
}
return 0;
}