Cod sursa(job #601947)

Utilizator DwarfmicDragos Bunea Dwarfmic Data 8 iulie 2011 15:46:26
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include<stdio.h>
#include<algorithm>
#define NMAX 100666

 using namespace std;

 int n,l,x,dwarf,OMG,aux,hip[NMAX];

 unsigned long solutie;

 struct nushtu
{

 int nu,stiu;

}v[NMAX];

 int fiust(int god)
{
 return god*2;
}
 int fiudr(int god)
{
 return god*2+1;
}
 int tata(int god)
{
 return god/2;
}

 void josheap(int god)
{
 int fiu;

 do{fiu=0;
    if(fiust(god)<=dwarf)
      {
       fiu=fiust(god);
       if(fiudr(god)<=dwarf&&hip[fiust(god)]<hip[fiudr(god)])
	 {fiu=fiudr(god);}
	  if(hip[fiu]<hip[god])
	     fiu=0;
      }
    if(fiu)
      {aux=hip[fiu];
       hip[fiu]=hip[god];
       hip[god]=aux;
       god=fiu;}
   }while(fiu);
}

 void susheap(int god)
{
 while(tata(god)>0&&hip[tata(god)]<hip[god])
      {
       aux=hip[god];
       hip[god]=hip[tata(god)];
       hip[tata(god)]=aux;
       god=tata(god);
      }
}
 int cmp(str x,str y)
{
 return (x.nu>y.nu);
}
 void introductiune(int god)
{
 hip[++dwarf]=god;
 susheap(dwarf);
}
 void excluziune(int god)
{
 hip[god]=hip[dwarf];
 hip[dwarf--]=0;
 if(tata(god)>0&&hip[god]>hip[tata(god)])
 susheap(god);
 else
 josheap(god);
}

 int main()
{
 freopen("lupu.in","r",stdin);
 freopen("lupu.out","w",stdout);

 int i,ct;

 scanf("%d%d%d",&n,&x,&l);

 for(i=1;i<=n;i++)
    {
     scanf("%d%d",&v[i].nu,&v[i].stiu);
     v[i].nu=(x-v[i].nu)/l+1;
    }

 sort(v+1,v+n+1,cmp);

 int ct;

 for(i=v[1].nu,ct=1;i>=1&&ct<=n;i--)
    {
     while(v[ct].nu==i&&ct<=n)
	  {
	   introductiune(v[ct++].stiu);
	  }
     if(dwarf)
     {
      solutie+=hip[1];
      excluziune(1);
     }
    }
 printf("%lu",solutie);
 return 0;
}