Cod sursa(job #602139)

Utilizator redls_95Nechita Laura redls_95 Data 9 iulie 2011 12:27:53
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include<cstdio>
#include<algorithm>
struct point
{
   int x,y;
};
using namespace std;
point v[100000];
int n1,n,h[100000];
long long s;
bool comp(point a,point b)
{
	return a.x<b.x;
}
void up(int k)
{
	int tata=0,aux;
	do
	{
		tata=0;
		if(k/2>=1 && h[k/2]<h[k])
		{
			aux=h[k];
			h[k]=h[k/2];
			h[k/2]=aux;
			k=k/2;
			tata=1;
		}
		else tata=0;
	}while(tata!=0 && k>1);
}
void down(int k)
{
	int fiu=0,aux;
	do
	{
		fiu=0;
		if(2*k<=n)
			fiu=2*k;
		if(2*k+1<=n &&h[fiu]<h[2*k+1])
			fiu=2*k+1;
		if(h[fiu]>h[k])
		{
			aux=h[k];
			h[k]=h[fiu];
			h[fiu]=aux;
            k=fiu;
		}
		else fiu=0;
	}while(fiu!=0);
}
void build()
{
	int i;
	for(i=n/2;i>=1;i--)
	down(i);
}
void inserare(int val)
{
   int t;
   h[++n]=val;
   t=n;
   up(t);
}
void stergere(int k)
{
   int i,j;
   s=s+h[k];
   h[k]=h[n];
   n--;
   if (h[k]>h[k/2]) up(k);
   else down(k);
}
int main()
{
   freopen("lupu.in","r",stdin);
   freopen("lupu.out","w",stdout);
   int x1,l,i,j,k,p=0;
   scanf("%d%d%d",&n1,&x1,&l);
   for(i=1;i<=n1;i++) scanf("%d%d",&v[i].x,&v[i].y);
   sort(v+1,v+n1+1,comp);
   k=0;
   n=0;
   for(i=1;i<=n1;i++)
   {
	   if(v[i].x==0)
	   {
		   inserare(v[i].y);
		   p++;
	   }
	   else
		   if(p!=0){
			   stergere(1);
			   p=0;
		   }
		if(v[i].x/l==k && v[i].x!=0)
		{
			inserare(v[i].y);
		}
		else
		{
			if(v[i].x!=0 &&v[i].x<=x1)
			{
			k++;
			stergere(1);
			inserare(v[i].y);
			}
		
		}
   }
  //stergere(1);
    printf("%lld",s);  
   return 0;
}