Cod sursa(job #3328263)

Utilizator iccjocIoan CHELARU iccjoc Data 7 decembrie 2025 13:57:40
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <bits/stdc++.h>
using namespace std;

class SchiSegmentTree
{
	int tree_size = 0;
	vector<long long> tree;
public:
	explicit SchiSegmentTree(int n)
	{
		this->tree.resize(4 * n + 20, LLONG_MAX);
		tree_size = n;
	}
	explicit SchiSegmentTree(int n, int value)
	{
		this->tree.resize(4 * n + 20, value);
		tree_size = n;
	}
	void update(int position, int value)
	{
		update_helper(1, 1, tree_size, position, value);
	}
	long long query(int position)
	{
		return query_helper(1, 1, tree_size, position);
	}
	void initialize()
	{
		initialize(1, 1, tree_size);
	}
private:
	void update_helper(int node, int left, int right, int position, int value)
	{
		if(left == right)
		{
			tree[node] = value;
		}
		else
		{
			int middle = (left + right) / 2;
			if(position <= middle)
			{
				update_helper(node * 2, left, middle, position, value);
			}
			else
			{
				update_helper(node * 2 + 1, middle + 1, right, position, value);
			}
			tree[node] = tree[node * 2] + tree[node * 2 + 1];
		}
	}
	long long query_helper(int node, int left, int right, int query)
	{
		if(left == right)
		{
			return left;
		}
		else
		{
			int middle = (left + right) / 2;
			long long left_min = LLONG_MAX, right_min = LLONG_MAX;
			if(tree[node * 2] >= query)
			{
				return query_helper(node * 2, left, middle, query);
			}
			else
			{
				return query_helper(node * 2 + 1, middle + 1, right, query - tree[node * 2]);
			}
		}
	}
	void initialize(int node, int left, int right)
	{
		if(left == right)
		{
			tree[node] = 1;
			return;
		}
		int mid = (left + right) / 2;
		initialize(node * 2, left, mid);
		initialize(node * 2 + 1, mid + 1, right);
		tree[node] = tree[node * 2] + tree[node * 2 + 1];
	}
};

int main()
{
	freopen("schi.in", "r", stdin);
	freopen("schi.out", "w", stdout);
	int n;
	cin >> n;
	vector<long long> v(n + 1), ans(n + 1);
	for(int i = 1; i <= n; i++)
	{
		cin >> v[i];
	}
	SchiSegmentTree st(n, 0);
	st.initialize();
	for(int i = n; i >= 1; i--)
	{
		int p = st.query(v[i]);
		ans[p] = i;
		st.update(p, 0);
	}
	for(int i = 1; i <= n; i++)
	{
		cout << ans[i] << "\n";
	}
}