Cod sursa(job #1847562)

Utilizator dan89Stan Alexandru dan89 Data 14 ianuarie 2017 18:47:47
Problema Schi Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#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;
}