Cod sursa(job #1033694)

Utilizator george_stelianChichirim George george_stelian Data 17 noiembrie 2013 14:41:43
Problema Lupul Urias si Rau Scor 32
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <cstdio>
#include <algorithm>

using namespace std;

struct lup
{
    int a,b;
};

lup v[100010],aux;
long long int h[100010],s;
int a,b,i,nr,k,mid,d,x,n;

void sort1(int st,int dr)
{
    int i=st,j=dr;
    mid=v[(i+j)/2].a;
    do
    {
        while(v[i].a>mid) i++;
        while(v[j].a<mid) j--;
        if(i<=j)
        {
            aux=v[i];v[i]=v[j];v[j]=aux;
            i++;j--;
        }
    }while(i<=j);
    if(i<dr) sort1(i,dr);
    if(j>st) sort1(st,j);
}

void upheap(int i)
{
    if(i/2 && h[i]>h[i/2])
    {
        swap(h[i],h[i/2]);
        upheap(i/2);
    }
}

void downheap(int i)
{
    if(i*2+1<=k && h[i]<h[i*2+1] && h[i*2+1]>=h[i*2])
    {
        swap(h[i],h[i*2+1]);
        downheap(i*2+1);
    }
    else if(i*2<=k && h[i]<h[i*2] && h[i*2]>=h[i*2+1])
        {
            swap(h[i],h[i*2]);
            downheap(i*2);
        }
}

int main()
{
    freopen("lupu.in", "r", stdin);
    freopen("lupu.out", "w", stdout);
    scanf("%d%d%d",&n,&d,&x);
    for(i=0;i<n;i++)
    {
        scanf("%d%d",&a,&b);
        if(a<=d)
        {
            v[++nr].a=1+(d-a)/x;
            v[nr].b=b;
        }
    }
    sort1(1,nr);
    h[++k]=v[1].b;
    for(i=2;i<=nr;i++)
    {
        if(v[i].a==v[i-1].a)
        {
            h[++k]=v[i].b;
            upheap(k);
        }
        else
        {
            s+=h[1];
            h[1]=v[i].b;
            downheap(1);
        }
    }
    s+=h[1];
    printf("%lld",s);
    return 0;
}