Cod sursa(job #2956215)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 18 decembrie 2022 18:42:47
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.78 kb
//Ilie Dumitru
#include<cstdio>
#include<algorithm>
const int NMAX=30005;

struct segTreeNode
{
	int x;
	friend segTreeNode operator+(segTreeNode a, segTreeNode b)
	{
		return {a.x+b.x};
	}
};

struct segTree
{
	int N;
	segTreeNode v[NMAX<<2];

	void init(int _N, segTreeNode* _v)
	{
		N=_N;
		build(0, 0, N-1, _v);
	}

	void initDefault(int _N, segTreeNode& defaultVal)
	{
		N=_N;
		buildDefault(0, 0, N-1, defaultVal);
	}

	void build(int node, int l, int r, segTreeNode* _v)
	{
		if(l==r)
		{
			v[node]=_v[l];
		}
		else
		{
			const int mid=l+((r-l)>>1);
			build((node<<1)|1, l, mid, _v);
			build((node<<1)+2, mid+1, r, _v);
			v[node]=v[(node<<1)|1]+v[(node<<1)+2];
		}
	}

	void buildDefault(int node, int l, int r, segTreeNode& defVal)
	{
		if(l==r)
		{
			v[node]=defVal;
		}
		else
		{
			const int mid=l+((r-l)>>1);
			buildDefault((node<<1)|1, l, mid, defVal);
			buildDefault((node<<1)+2, mid+1, r, defVal);
			v[node]=v[(node<<1)|1]+v[(node<<1)+2];
		}
	}

	/*void propag(int node, int l, int r)
	{
		if(v[node].lazy)
		{
			if(l!=r)
			{
				v[(node<<1)|1].lazy+=v[node].lazy;
				v[(node<<1)+2].lazy+=v[node].lazy;
			}
			v[node].x+=v[node].lazy;
			v[node].lazy=0;
		}
	}*/

	segTreeNode query(int l, int r) {return query(0, 0, N-1, l, r);}
	segTreeNode query(int node, int l, int r, int st, int dr)
	{
		if(st<=l && r<=dr)
			return v[node];
		const int mid=l+((r-l)>>1);
		if(dr<=mid)
			return query((node<<1)|1, l, mid, st, dr);
		if(mid<st)
			return query((node<<1)+2, mid+1, r, st, dr);
		return query((node<<1)|1, l, mid, st, dr)+query((node<<1)+2, mid+1, r, st, dr);
	}

	int findKth0(int K) {return findKth0(0, 0, N-1, K);}
	int findKth0(int node, int l, int r, int K)
	{
		if(l==r)
			return l;
		int mid=l+((r-l)>>1);
		if(mid-l+1-v[(node<<1)|1].x>K)
			return findKth0((node<<1)|1, l, mid, K);
		return findKth0((node<<1)+2, mid+1, r, K-(mid-l+1-v[(node<<1)|1].x));
	}

	void update(int pos, segTreeNode& x) {update(0, 0, N-1, pos, x);}
	void update(int node, int l, int r, int pos, segTreeNode& x)
	{
		if(l==r)
		{
			v[node]=x;
		}
		else
		{
			const int mid=l+((r-l)>>1);
			if(pos<=mid)
				update((node<<1)|1, l, mid, pos, x);
			else
				update((node<<1)+2, mid+1, r, pos, x);
			v[node]=v[(node<<1)|1]+v[(node<<1)+2];
		}
	}
};
segTree S;
int v[NMAX];
int ans[NMAX];

int main()
{
	FILE *f=fopen("schi.in", "r");
	FILE *g=fopen("schi.out", "w");
	int i, N, aux;
	segTreeNode x;
	fscanf(f, "%d", &N);
	for(i=0;i<N;++i)
		fscanf(f, "%d", v+i), --v[i];
	x.x=0;
	S.initDefault(N, x);
	for(i=N-1;i>-1;--i)
	{
		aux=S.findKth0(v[i]);
		ans[aux]=i+1;
		x.x=1;
		S.update(aux, x);
	}
	for(i=0;i<N;++i)
		fprintf(g, "%d\n", ans[i]);
	fclose(f);
	fclose(g);
	return 0;
}