Cod sursa(job #1626128)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 2 martie 2016 22:44:38
Problema Schi Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <bitset>
#include <stack>
#include <iomanip>
#include <fstream>
#define MOD 105011
#define NMAX 30005
#define INF 0x3f3f3f3f
#define pb push_back

using namespace std;

FILE *fin = freopen("schi.in", "r", stdin);
FILE *fout = freopen("schi.out", "w", stdout);

typedef pair<int, int> pii;

int v[NMAX];
pii clasament[NMAX];
short ai[4 * NMAX];
int n, qst, qdr, ansQ, pozUpdate;

void build(int nod, int st, int dr) {
	if (st == dr) {
		ai[nod] = 1;
		return;
	}

	int mid = (st + dr) >> 1, fs = (nod << 1);
	build(fs, st, mid);
	build(fs + 1, mid + 1, dr);

	ai[nod] = ai[fs] + ai[fs + 1];
}

void query(int nod, int st, int dr) {
	if (dr<qst || st>qdr)
		return;

	if (qst <= st && qdr >= dr) {
		ansQ += ai[nod];
		return;
	}

	int mid = (st + dr) >> 1, fs = (nod << 1);
	if (qst <= mid)
		query(fs, st, mid);
	if (mid < qdr)
		query(fs + 1, mid + 1, dr);
}

void update(int nod, int st, int dr) {
	if (st == dr) {
		ai[nod] = 0;
		return;
	}

	int mid = (st + dr) >> 1, fs = (nod << 1);
	if (pozUpdate <= mid)
		update(fs, st, mid);
	else
		update(fs + 1, mid + 1, dr);

	ai[nod] = ai[fs] + ai[fs + 1];
}

int binSearch(int x) {
	int st, dr, mid, res;

	st = 1;
	dr = n;
	while (st <= dr) {
		mid = (st + dr) >> 1;

		qst = 1;
		qdr = mid;
		ansQ = 0;
		query(1, 1, n);
		if (ansQ == x)
			res = mid;

		if (ansQ < x)
			st = mid + 1;
		else
			dr = mid - 1;
	}

	return res;
}

int main() {
	int i, poz, aux;

	scanf("%d", &n);

	for (i = 1; i <= n; ++i)
		scanf("%d", &v[i]);

	build(1, 1, n);
	for (i = n; i > 0; --i) {
		poz = binSearch(v[i]);
		clasament[i].first = poz;
		clasament[i].second = i;
		pozUpdate = poz;
		update(1, 1, n);
	}

	sort(clasament + 1, clasament + n + 1);
	for (i = 1; i <= n; ++i)
		printf("%d\n", clasament[i].second);

	return 0;
}