Cod sursa(job #1147614)

Utilizator ELHoriaHoria Cretescu ELHoria Data 19 martie 2014 23:17:57
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <fstream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
#include <sstream>

using namespace std;

class IntervalTree {
	vector<unsigned short> sum;
	int n;

	int leftSon(const int& node) {
		return node << 1;
	}

	int rightSon(const int& node) {
		return (node << 1) + 1;
	}

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

		int mid = (l + r) >> 1;
		buildTree(leftSon(node), l, mid);
		buildTree(rightSon(node), mid + 1, r);
		sum[node] = sum[leftSon(node)] + sum[rightSon(node)];
 	}

	public:

		IntervalTree(int n_ = 1) {
			n = n_;
			sum.resize(n << 2);
			buildTree(1, 1, n);
		}

		void update(int node, int l, int r, int pos) {
			if (l == r) {
				sum[node] = 0;
				return;
			}

			int mid = (l + r) >> 1;

			if (pos <= mid) {
				update(leftSon(node), l, mid, pos);
			} else {
				update(rightSon(node), mid + 1, r, pos);
			}
			sum[node] = sum[leftSon(node)] + sum[rightSon(node)];
		
		}

		int query(int node, int l, int r,int x) {
			if (l == r) {
				return l;
			}

			int mid = (l + r) >> 1;
			if (sum[leftSon(node)] < x) {
				return query(rightSon(node), mid + 1, r, x - sum[leftSon(node)]);
			} 

			return query(leftSon(node), l, mid, x);
		}
	
};

int main()
{
	ifstream cin("schi.in");
	ofstream cout("schi.out");
	int n;
	cin >> n;
	vector<int> p(n);
	vector<int> ret(n);
	IntervalTree tree(n);

	for (int i = 0; i < n; i++) {
		cin >> p[i];
		ret[i] = i;
	}

	for (int i = n - 1; i >= 0; i--) {
		p[i] = tree.query(1, 1, n, p[i]);
		tree.update(1, 1, n, p[i]);
	}

	sort(ret.begin(), ret.end(), [&](const int& i, const int& j) {
		return p[i] < p[j];
	});

	for (int i = 0; i < n; i++) {
		cout << ret[i] + 1 << "\n";
	}

	return 0;
}