Cod sursa(job #347130)

Utilizator taloibogdanTaloi Bogdan Cristian taloibogdan Data 11 septembrie 2009 09:52:11
Problema Lupul Urias si Rau Scor 44
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
struct che{long d,l,r;}a[600010];
long n,l,i,lh,ru,x,hh,h[600010];
long long lna;
long cmp(che a,che b)
{if(a.r>b.r)return 1;
return 0;}
int main()
{
 freopen("lupu.in","r",stdin);
 freopen("lupu.out","w",stdout);
 scanf("%ld%ld%ld",&n,&x,&l);
 for(i=1;i<=n;++i)
    {scanf("%ld%ld",&a[i].d,&a[i].l);   
     a[i].r=(x-a[i].d)/l+1;
     if(x<a[i].d){--i;--n;}}
 sort(a+1,a+n+1,cmp);
 lh=0;
 lna=0;
 ru=a[1].r;
 for(i=1;i<=n;++i)   
  {if(a[i].r==ru)
   {++lh;
   h[lh]=i;
   x=lh;
   while(a[h[x]].l>a[h[x/2]].l&&x>1){hh=h[x];h[x]=h[x/2];h[x/2]=hh;x/=2;}}
   
   while(a[i+1].r!=ru)
     {if(lh==0){ru=a[i+1].r;break;}
      ru--;
      lna+=a[h[1]].l;
      h[1]=h[lh--];
      if(lh)
      {x=1;
      while(a[h[x]].l<a[h[2*x]].l||a[h[x]].l<a[h[2*x+1]].l)
        if(a[h[2*x]].l>a[h[2*x+1]].l){swap(h[2 * x],h[x]);x*=2;}
                                else {swap(h[2 * x + 1],h[x]);x=x*2+1;}}}}
 printf("%lld\n",lna); 
 return 0;   
}