Cod sursa(job #331546)

Utilizator DraStiKDragos Oprica DraStiK Data 14 iulie 2009 13:49:40
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <algorithm>
#define DIM 100005
using namespace std;

struct nod {int x;
            nod *urm;} *lst[DIM];
int h[DIM],d[DIM],a[DIM],t[DIM];
int n,x,l,m,nrt,tmax,p;

void read ()
{
    int i,nr;
    scanf ("%d%d%d",&n,&x,&l);
    for (i=1; i<=n; ++i)
    {
        scanf ("%d%d",&nr,&a[i]);
        if (nr<=x)
            h[i]=d[i]=(x-nr)/l+1;
    }
}

int cbin (int val)
{
    int st,dr,mij,sol;
    for (st=1, dr=p; st<=dr; )
    {
        mij=(st+dr)/2;
        if (h[mij]==val)
            sol=mij;
        if (h[mij]<val)
            st=mij+1;
        else
            dr=mij-1;
    }
    return sol;
}

void norm ()
{
    int i;
    sort (h+1,h+n+1);
    for (i=p=1; i<=n; ++i)
        if (h[i]!=h[p])
            h[++p]=h[i];
    for (i=1; i<=n; ++i)
    {
        t[i]=cbin (d[i]);
        if (t[i]>tmax)
            tmax=t[i];
    }

}

void add (int a,int b)
{
    nod *p=new nod;
    p->x=b;
    p->urm=lst[a];
    lst[a]=p;
}

void init ()
{
    int i;
    for (i=1; i<=n; ++i)
        if (d[i])
            add (t[i],a[i]);
}

void swap (int &a,int &b)
{
    int aux=a;
    a=b;
    b=aux;
}

void upheap (int nod)
{
    for (; nod>1 && h[nod]>h[nod/2]; nod/=2)
        swap (h[nod],h[nod/2]);
}

void downheap (int nod)
{
    int son;
    do
    {
        son=0;
        if (2*nod<=m)
        {
            son=2*nod;
            if (2*nod+1<=m && h[2*nod+1]>h[2*nod])
                son=2*nod+1;
            if (h[son]<=h[nod])
                son=0;
        }
        if (son)
        {
            swap (h[nod],h[son]);
            nod=son;
        }
    }
    while (son);
}

void solve ()
{
    nod *p;
    int i;
    for (i=tmax; i>=1; --i)
    {
        for (p=lst[i]; p; p=p->urm)
        {
            h[++m]=p->x;
            upheap (m);
        }
        if (m)
        {
            nrt+=h[1];
            h[1]=h[m--];
            downheap (1);
        }
    }
    printf ("%d",nrt);
}

int main ()
{
    freopen ("lupu.in","r",stdin);
    freopen ("lupu.out","w",stdout);
    read ();
    norm ();
    init ();
    solve ();
    return 0;
}