Cod sursa(job #1724500)

Utilizator tudi98Cozma Tudor tudi98 Data 3 iulie 2016 13:17:35
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <bits/stdc++.h>
using namespace std;
#define Nmax 30000

int N;
int A[Nmax+1];
int Sol[Nmax+1];
int data[Nmax*4+4];

void Build_Tree(int node,int l,int r)
{
    if (l == r)
    {
        data[node] = 1;
        return;
    }

    int mid = (l+r)>>1;
    Build_Tree(node<<1,l,mid);
    Build_Tree(node<<1|1,mid+1,r);

    data[node] = data[node<<1] + data[node<<1|1];
}

int Query(int node,int l,int r,int p)
{
    if (l == r)
    {
        data[node] = 0;
        return l;
    }

    int mid = (l+r)>>1;
    int Sol = 0;
    if (data[node<<1] < p)
        Sol = Query(node<<1|1,mid+1,r,p-data[node<<1]);
    else
        Sol = Query(node<<1,l,mid,p);

    data[node] = data[node<<1] + data[node<<1|1];
    return Sol;
}

int main()
{
    ifstream fin("schi.in");
    ofstream fout("schi.out");

    fin >> N;
    for (int i = 1; i <= N; i++)
        fin >> A[i];

    Build_Tree(1,1,N);

    for (int i = N; i >= 1; i--)
        Sol[Query(1,1,N,A[i])] = i;

    for (int i = 1; i <= N; i++)
        fout << Sol[i] << "\n";
}