Cod sursa(job #916315)

Utilizator cat_red20Vasile Ioana cat_red20 Data 16 martie 2013 12:29:00
Problema Lupul Urias si Rau Scor 4
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,l,x,h[100001],maxh;
long long sol;
struct oaie
{
    int t;
    int b;
}v[100001];


void citire()
{
    int d;
    freopen("lupu.in","r",stdin);
    scanf("%d %d %d",&n,&x,&l);
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d",&d,&v[i].b);
        if(x>d)
        v[i].t=(x-d)/l+1;
    }
}

int cmp(oaie a,oaie b)
{
    if(a.t==b.t)
    return a.b>b.b;
    return a.t>b.t;
}

void promovare(int nod)
{
    int val=h[nod];
    while(h[nod]>h[nod/2] && nod>1)
    {
        h[nod]=h[nod/2];
        nod=nod/2;
    }
    h[nod]=val;
}

void AdaugaNoduri(int poz,int t)
{
    while(v[poz].t==t)
    {
        h[++maxh]=v[poz].b;
        promovare(maxh);
        poz++;
    }
}

void stergere(int nod)
{
    int t;
    h[nod]=h[maxh--];
    int st,dr,max;
    while(2*nod<=maxh)
    {
        st=2*nod;
        dr=2*nod+1;
        max=nod;
        if(h[st]>h[max])
        max=st;
        if(dr<=maxh && h[dr]>h[max])
        max=dr;
        if(max!=nod)
        {
            t=h[max];
            h[max]=h[nod];
            h[nod]=t;
            nod=max;
        }
        else
        break;
    }
}

void parcurgere()
{
    int j=1;
    for(int i=v[1].t;i>=1;i--)
    {
        while(v[j].t>i)
        {
            j++;
        }
        if(v[j].t==i)
        {
            AdaugaNoduri(j,i);
        }
        if(maxh>=1)
        {
            sol+=h[1];
            stergere(1);
        }
    }
}

void afisare()
{
    freopen("lupu.out","w",stdout);
    printf("%lld",sol);
}

int main()
{
    citire();
    sort(v+1,v+n+1,cmp);
    parcurgere();
    afisare();
    return 0;
}