Cod sursa(job #527)

Utilizator mariusdrgdragus marius mariusdrg Data 11 decembrie 2006 14:31:29
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 kb
#include<stdio.h>
#include<algorithm>
typedef int oi[3];

const int maxn = 610000;

oi a[maxn];
long long h[maxn];
long long n,x,v,i;
long long s;
long long l,ind[maxn];


using namespace std;

bool cmpf(const long long &i,const long long &j)
{
        return a[i][1]>a[j][1];
}

void pop(long long poz)
{
        while (h[poz]>h[poz/2]&&poz>1)
        {
                long long aux=h[poz];
                h[poz]=h[poz/2];
                h[poz/2]=aux;
                poz=poz/2;
        }

}

void push(long long poz)
{
        while((h[poz] < h[poz*2] && poz * 2 <= l)||(h[poz] < h[poz * 2 + 1] && poz * 2 + 1 <= l))
        {
                if (h[poz*2]>h[poz*2+1]||(poz*2+1>l))
                {
                        long long aux=h[poz];
                        h[poz]=h[poz*2];
                        h[poz*2]=aux;
                        poz*=2;
                }
                else
                {
                        long long aux=h[poz*2+1];
                        h[poz*2+1]=h[poz];
                        h[poz]=aux;
                        poz=poz*2+1;
                }

  
        }

}


long long ad(long long i)
{
        l++;
        h[l]=i;
        pop(l);

}

long long rem()
{
        long long aux=h[1];
        h[1]=h[l];
        h[l]=0;
        if (l>=1)l--;
        push(1);
        return (long long ) aux;

}

int main()
{
        freopen("lupu.in","r",stdin);
        freopen("lupu.out","w",stdout);
        scanf("%lld %lld %lld",&n,&x,&v);
        for(i=1;i<=n;i++)
        {
                scanf("%lld %lld",&a[i][1],&a[i][2]);
                long long aux=1;
                a[i][1]=(x-a[i][1])/v+aux;
                if (a[i][1]<0)
                {
                        i--;
                        n--;
                }
                ind[i]=i;
        }
        
        sort(ind+1,ind+n+1,cmpf);

        long long aux=a[ind[1]][1];
        long long j=1;
        for(i=1;i<=n;i++)
        {

                if (a[ind[i]][1]!=aux)
                {
                        for(j=aux;j>a[ind[i]][1];j--)
                                s+=(long long )rem();
                        aux=a[ind[i]][1];
                }
                ad(a[ind[i]][2]);
        }
        for(j=a[ind[n]][1];j>0;--j)
                s+=(long long)rem();
        printf("%lld",s);
        return 0;



}