Cod sursa(job #60736)

Utilizator moga_florianFlorian MOGA moga_florian Data 16 mai 2007 12:08:26
Problema Lupul Urias si Rau Scor 56
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include<stdio.h>
#define Nmax 100005

int p[Nmax],d[Nmax];
int arb[2*Nmax],li[2*Nmax],lf[2*Nmax];
int poz[Nmax];

int query(int i,int a,int b)
{  
if(b<li[i] || a>lf[i])
   return 0;
      
if(a<=li[i] && lf[i]<=b)
   return arb[i];

int r1,r2;   
r1=query(2*i,a,b);
r2=query(2*i+1,a,b);

if(r1>r2)
  return r1;
return r2;    
}

void add(int i)
{
int k=poz[i];
arb[k]=0;
k>>=1;
     
while(k)
  {
  if(arb[2*k]>arb[2*k+1])
     arb[k]=arb[2*k];
  else
     arb[k]=arb[2*k+1];
     
  k>>=1;  
  }
}

void go(int i, int a,int b)
{
li[i]=a;
lf[i]=b;
arb[i]=b;

if(a==b)
   {
   poz[a]=i;
   return;
   }

int mij=(a+b)>>1;
go(2*i,a,mij);
go(2*i+1,mij+1,b);
}

void intersc(int i,int j)
{
p[i]^=p[j];
p[j]^=p[i];
p[i]^=p[j];

d[i]^=d[j];
d[j]^=d[i];
d[i]^=d[j];     
}

int main()
{
FILE *fin=fopen("lupu.in","r"),
     *fout=fopen("lupu.out","w");
     
int N,X,L,i,j,k;

fscanf(fin,"%d%d%d",&N,&X,&L);
for(i=1;i<=N;i++)
  {
  fscanf(fin,"%d%d",&d[i],&p[i]);
  j=i;
  while(j/2 && (p[j/2]>p[j] || (p[j/2]==p[j] && d[j/2]<d[j]) ) )
     {
     intersc(j/2,j);
     j>>=1;       
     }
  }
  
i=N;
while(i>1)
 {
 intersc(1,i);
 i--;
 
 j=1;
 while(1)
   {
   k=j<<1;
   if(k>i) break;
   if(k+1<=i && (p[k+1]<p[k] || (p[k+1]==p[k] && d[k+1]>d[k]) ) ) k++;         
   if(p[j]<p[k] || (p[j]==p[k] && d[j]>d[k]) ) break;
   
   intersc(j,k);
   j=k;
   }               
 }
  
//arborele
go(1,1,N);

int ok=1;
long long sol=0;
for(i=1;i<=N;i++)
// if((X-d[i])/L > 0)
  {
  k=(X-d[i])/L;
  if(k>N)
    k=N;
    
  j=query(1,1,k);
  if(j>0)
    {
    sol+=(long long)p[i];
    add(j);
    }  
  else
    if(ok)
      {
      sol+=(long long)p[i];
      ok=0;
      }
  }
     
fprintf(fout,"%lld\n",sol);

fclose(fin);
fclose(fout);
return 0;         
}