Cod sursa(job #43511)

Utilizator ZuziFilip Sanziana Zuzi Data 30 martie 2007 11:14:30
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <stdio.h>
#define NMAX 1 << 17
//#define NMAX 101
int n, a[NMAX], p, l;
int dm;
unsigned int sol;

typedef struct
{
	int t, x;
}VEC;
VEC t[NMAX];

void read()
{
	int i,d;
	scanf("%d%d%d", &n, &p, &l);
	for (i = 1; i <= n; i++)
	{
		scanf("%d%d", &d, &t[i].x);
		t[i].t = (p-d) / l+1;
	}
}


void rec_heap(int i)
{
	int st, dr, maxim, aux;
	while (i<=dm)
	{
		st = 2*i; dr = 2*i+1;
		if (st <= dm && a[st] > a[i])
			maxim = st;
		else
			maxim = i;
		if (dr <= dm && a[dr] > a[maxim])
			maxim = dr;
		if (i != maxim)
		 {
			aux = a[i];
			a[i] = a[maxim];
			a[maxim] = aux;
			i = maxim;
		 }
		else
			i=dm+1;
	}
}

int extragere_maxim()
{
	if (dm == 0) return 0;
	int v =a [1];
	a[1] = a[dm--];
	rec_heap(1);
	return v;
}


void insert_heap(int v)
{
	int i,t,aux;
	a[++dm] = v;
	for (i = dm; i > 1; i = i/2)
	{
		t=i/2;
		if (a[t]<a[i])
		 aux = a[t], a[t] = a[i], a[i] = aux;
		else
		 i = 1;
	}

}

int partitie(int st, int dr)
{
	int i, j;
	VEC aux, pivot;
	i=st-1;
	j=dr+1;
	pivot=t[(st+dr)/2];
	while (1)
	{
		do {++i;} while (t[i].t>pivot.t || (t[i].t==pivot.t && t[i].x>pivot.x));
		do {--j;} while (t[j].t<pivot.t || (t[j].t==pivot.t && t[j].x<pivot.x));
		if (i<j)
			{ aux=t[i]; t[i]=t[j]; t[j]=aux;}
		else
			return j;
	}
}


void sort(int st, int dr)
{
	int m;
	if (st < dr)
	{
		m = partitie(st, dr);
		sort(st, m);
		sort(m+1, dr);
	}
}

void rezolv()
{
	int j, i;
	sort(1,n);

	for (i = t[1].t, j = 1; i; --i)
	 {
	 	for (; j <= n && t[j].t == i; j++)
		  insert_heap(t[j].x);

		sol += extragere_maxim();

	 }


}

int main()
{
	freopen("lupu.in", "r", stdin);
	freopen("lupu.out", "w", stdout);
	read();
	rezolv();
	printf("%d\n", sol);
	return 0;
}