Cod sursa(job #347134)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 11 septembrie 2009 10:00:18
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
struct vect
{
	int t,x;
};
int n,x,l,u,nr;
int st[100005];
int heap[1000005];
vect v[100005];

bool comp(vect a, vect b)
{
	return a.t>b.t;
}

void read()
{
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	scanf("%d%d%d",&n,&x,&l);
	int i;
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&v[i].t,&v[i].x);
		if(v[i].t>x)
		{
			n--;
			i--;
			continue;
		}
		v[i].t=(x-v[i].t)/l+1;
	}
}

void heap_up(int nod)
{
	if((nod>>1)==0)
		return;
	if(heap[nod>>1]<heap[nod])
	{
		int aux;
		aux=heap[nod>>1];
		heap[nod>>1]=heap[nod];
		heap[nod]=aux;
		heap_up(nod>>1);
	}
}

void heap_down(int nod)
{
	int fiu=nod;
	if((nod<<1)<=nr && heap[nod<<1]>heap[fiu])
		fiu=(nod<<1);
	if((nod<<1)+1<=nr && heap[(nod<<1)+1]>heap[fiu])
		fiu=(nod<<1)+1;
	if(fiu!=nod)
	{
		int aux;
		aux=heap[fiu];
		heap[fiu]=heap[nod];
		heap[nod]=aux;
		heap_down(fiu);
	}
}

void rez()
{
	int i,j,lim;
	long long s=0;
	for(i=1;i<=n;i++)
		if(v[i].t!=v[i+1].t)
		{
			heap[++nr]=v[i].x;
			heap_up(nr);
			lim=v[i].t-v[i+1].t;
			for(j=1;j<=lim && nr;j++)
			{
				s=s+heap[1];
				heap[1]=heap[nr];
				nr--;
				heap_down(1);
			}
		}
		else
		{
			heap[++nr]=v[i].x;
			heap_up(nr);
		}
	printf("%lld\n",s);
}

int main()
{
	read();
	sort(v+1,v+n+1,comp);
	rez();
	return 0;
}