Cod sursa(job #826754)

Utilizator UnforgivenMihai Catalin Botezatu Unforgiven Data 1 decembrie 2012 10:44:51
Problema Schi Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <fstream>
#define MAX_SIZE 30001
using namespace std;

ifstream input("schi.in");
ofstream output("schi.out");

typedef struct
{
    int value;
    int pos;
}st;

st tree[3 * MAX_SIZE];
int vect[MAX_SIZE];

int A;
int B;
int val;

void build_tree(int nod , int left , int right)
{
    if (left == right)
    {
        tree[nod].value = vect[left];
        tree[nod].pos = left;
        return;
    }
    int middle = (left + right) / 2;
    build_tree(2*nod , left , middle);
    build_tree(2*nod+1 , middle+1 , right);
    if (tree[2*nod+1].value <= tree[2*nod].value)
    {
        tree[nod] = tree[2*nod+1];
    }
    else
    {
        tree[nod] = tree[2*nod];
    }
}

void update_tree(int nod , int left , int right)
{
    if (A > B) return;
    if (left == right)
    {
        tree[nod].value += val;
        return;
    }
    int middle = (left + right) / 2;
    if (A <= middle) update_tree(2*nod , left , middle);
    if (middle < B) update_tree(2 * nod +1 ,middle+1,right);

    if (tree[2*nod+1].value <= tree[2*nod].value)
    {
        tree[nod] = tree[2*nod+1];
    }
    else
    {
        tree[nod] = tree[2*nod];
    }
}

int main()
{
    int N;
    input >> N;
    for (int i = 1;i<=N;i++)
    {
        input >> vect[i];
    }
    build_tree(1,1,N);
    for (int i = 1 ; i<=N;i++)
    {
        output << tree[1].pos << "\n";
        A = 1;
        B = tree[1].pos - 1;
        val = 1;
        update_tree(1,1,N);

        A = tree[1].pos;
        B = tree[1].pos;
        val = MAX_SIZE;

        update_tree(1,1,N);

    }
    input.close();
    output.close();

    return 0;
}