Cod sursa(job #1242019)

Utilizator yololy97Olaru Bogdan-Ioan yololy97 Data 13 octombrie 2014 21:26:45
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <cstdio>
#define N 30001
using namespace std;
int H[3 * N], n, v[N], p[N];
void build(int node, int L, int R){
	int M = (L + R) / 2;
	if(L == R)
		H[node] = 1;
	else{
		build(node * 2, L, M);
		build(node * 2 + 1, M + 1, R);
		H[node] = H[node * 2] + H[node * 2 + 1];
	}
}
void update(int node, int L, int R, int pos){
	int M = (L + R) / 2;
	if(L == R){
		H[node] = 0;
		return;
	}
	if(pos <= M)
		update(node * 2, L, M, pos);
	else
		update(node * 2 + 1, M + 1, R, pos);
	H[node] = H[node * 2] + H[node * 2 + 1];
}
int query(int node, int L, int R, int val){
	int M = (L + R) / 2;
	if(L == R)
		return L;
	if(H[node * 2] >= val)
		return query(node * 2, L, M, val);
	else
		return query(node * 2 + 1, M + 1, R, val - H[node * 2]);
}
int main(){
	freopen("schi.in", "r", stdin);
	freopen("schi.out", "w", stdout);
	scanf("%d ", &n);
	for(int i = 1; i <= n; ++i)
		scanf("%d ", &v[i]);
	build(1, 1, n);
	for(int i = n; i > 0; --i){
		int x = query(1, 1 , n, v[i]);
		p[x] = i;
		update(1, 1, n, x);
	}
	for(int i  = 1; i <= n; ++i)
		printf("%d\n", p[i]);
	return 0;
}