Cod sursa(job #1279832)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 30 noiembrie 2014 22:50:32
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<iostream>
#include<fstream>
using namespace std;

#define NMAX 30001

int a[4*NMAX+1],v[NMAX],sol[NMAX];

void build(int nod, int st, int dr)
{
	int mij;
	if(st==dr) {
		a[nod]=1;
		return ;
	}
	mij=(st+dr)/2;
	build(nod*2,st,mij);
	build(nod*2+1,mij+1,dr);
	a[nod]=a[nod*2]+a[nod*2+1];
}

void update(int nod, int st, int dr, int poz)
{
	int mij;
	if(st==dr) {
		a[nod]=0;
		return ;
	}
	mij=(st+dr)/2;
	if(poz<=mij)
		update(nod*2,st,mij,poz);
	else update(nod*2+1,mij+1,dr,poz);
	a[nod]=a[nod*2]+a[nod*2+1];
}

int query(int nod, int st, int dr, int k)
{
	int mij;
	if(st==dr)
		return st;
	mij=(st+dr)/2;
	if(k<=a[nod*2])
		return query(nod*2,st,mij,k);
	else return query(nod*2+1,mij+1,dr,k-a[nod*2]);
}

int main ()
{
	int i,x,n;
	ifstream f("schi.in");
	ofstream g("schi.out");
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i];
	f.close();
	build(1,1,n);
	for(i=n;i>=1;i--) {
		x=query(1,1,n,v[i]);
		update(1,1,n,x);
		sol[x]=i;
	}
	for(i=1;i<=n;i++)
		g<<sol[i]<<'\n';
	g.close();
	return 0;
}