Cod sursa(job #1463)

Utilizator megabyteBarsan Paul megabyte Data 13 decembrie 2006 18:58:33
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <stdio.h>
#define NMAX 100001
#define DAD(x) (x/2)
#define ST(x) (2*x)
#define DR(x) (2*x+1)
#define INF "lupu.in"
#define OUF "lupu.out"
unsigned long t[NMAX],a[NMAX];
struct heap
{
  unsigned long h[NMAX],dim;
  void init(unsigned long key);
  void insert(unsigned long key);
  void rebuild(unsigned long i);
  unsigned long max();
}m;
void heap::init(unsigned long key)
{
  dim=1;
  h[dim]=key;
}
void heap::insert(unsigned long key)
{
  dim++;
  register unsigned long i;
  i=dim;
  while(i>1&&h[DAD(i)]<key)
  {
    h[i]=h[DAD(i)];
    i=DAD(i);
  }
  h[i]=key;
}
void heap::rebuild(unsigned long i)
{
  unsigned long l,r,maxi;
  l=ST(i);
  r=DR(i);
  if(l<=dim&&h[l]>h[i]) maxi=l;
   else maxi=i;
  if(r<=dim&&h[r]>h[maxi]) maxi=r;
  if(maxi!=i)
   {
     l=h[i];h[i]=h[maxi];h[maxi]=l;
     rebuild(maxi);
   }
}
unsigned long heap::max()
{
  unsigned long maxi;
  if(dim>0)
  {
  maxi=h[1];
  h[1]=h[dim];dim--;
  rebuild(1);
  }
  else maxi=0;
  return maxi;
}

void qsort(unsigned long st,unsigned long dr)
{
     unsigned long i, j,aux, piv;
     i=st; j=dr;piv=t[i];
     do{ 
               while ( t [ i ] > piv ) i++;
               while ( t [ j ] < piv) j--;
               if(i<=j)
              {//interschimbi
                aux=a[i]; a[i]=a[j]; a[j]=aux;
                aux=t[i]; t[i]=t[j]; t[j]=aux;
                i++ ; j--;
              }
    }while(i<=j);
    if(i<dr)qsort(i,dr);
    if(j>st)qsort(st,j);
}
main()
{
  FILE *in,*out;
  in=fopen(INF,"r");
  out=fopen(OUF,"w");
  unsigned long n,x,l,v=0,tmax=0,p=0;
  register unsigned long i,j;
  unsigned long long s=0;
  fscanf(in,"%ld %ld %ld",&n,&x,&l);
  for(i=1;i<=n;i++) 
  {
   fscanf(in,"%ld %ld",&v,a+i);
   t[i]=(v<=x)?((x-v)/l+1):(0);
  }
  qsort(1,n);
  m.init(a[1]);tmax=t[1];
  i=2;
  while(t[i]==tmax){ m.insert(a[i]);i++;}
  s+=m.max();tmax--;
  while(tmax>0)
  {
     if(tmax==t[i])
     {
       x=t[i];
       while(t[i]==x&&i<n)
       {
         m.insert(a[i]);
         i++;
       }
     }
     s+=m.max();
     tmax--;
  }
  fprintf(out,"%lld ",s);
  fclose(in);fclose(out);
}