Cod sursa(job #152600)

Utilizator CezarMocanCezar Mocan CezarMocan Data 9 martie 2008 16:28:22
Problema Lupul Urias si Rau Scor 4
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <cstdio>
#include <algorithm>

using namespace std;

struct oaie{long long t; long long p;};

long long n,i,j,x,l,d[100100], z[10010l], h[200100],p,s;
oaie t[100100];

bool cmp(oaie a, oaie b)
    {
    if (a.t>b.t)    
        return true;
    else
        return false;
    }
    
void adauga_heap(long long x)
    {
    long long poz,aux;
    p++;
    h[p]=x;
    poz=p;
    while ((h[poz]>h[poz/2])&&(poz>1))
        {
        aux=h[poz];
        h[poz]=h[poz/2];
        h[poz/2]=aux;
        poz/=2;
        }
    }
    
long long maxim(long long a, long long b)
    {
    if (a>b)
        return a;
       else
        return b;    
    }
    
void scoate_heap()
    {
    long long poz,mx,aux;
    h[1]=h[p];
    p--;
    poz=1;
    while ((h[poz]<maxim(h[poz*2],h[poz*2+1])))
        {
        mx=maxim(h[poz*2],h[poz*2+1]);
        if (mx==h[2*poz]) 
            {
            aux=h[poz];
            h[poz]=h[2*poz];
            h[2*poz]=aux;
            poz*=2;
            }
        else
            {
            aux=h[poz];
            h[poz]=h[2*poz+1];
            h[2*poz+1]=aux;   
            poz=poz*2+1;             
            }
            
        }
    }

int main(){
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
scanf("%lld%lld%lld",&n,&x,&l);
for (i=1;i<=n;++i)
    {
    scanf("%lld%lld",&d[i],&z[i]);
    t[i].t=(x-d[i])/l;
    t[i].p=i;
    }
sort(t+1,t+n+1,cmp);
/*for (i=1;i<=n;i++)
    printf("%d %d \n",t[i].t, t[i].p);*/
i=1;
while (i<=n)
    {
    j=i;
    while ((t[j].t==t[i].t)&&(j<=n))
        {
        adauga_heap(z[t[j].p]);
        ++j;            
        }
    s+=h[1];
    scoate_heap();
    i=j;
    }
printf("%lld",s);
return 0;
}