Cod sursa(job #1321104)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 18 ianuarie 2015 19:33:38
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 1.75 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
struct vect
{
    int t,x;
};
int n,x,l,u,nr;
int st[100005];
int heap[1000005];
vect v[100005];

bool comp(vect a, vect b)
{
    return a.t>b.t;
}

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

void heap_up(int nod)
{
    if((nod>>1)==0)
        return;
    if(heap[nod>>1]<heap[nod])
    {
        int aux;
        aux=heap[nod>>1];
        heap[nod>>1]=heap[nod];
        heap[nod]=aux;
        heap_up(nod>>1);
    }
}

void heap_down(int nod)
{
    int fiu=nod;
    if((nod<<1)<=nr && heap[nod<<1]>heap[fiu])
        fiu=(nod<<1);
    if((nod<<1)+1<=nr && heap[(nod<<1)+1]>heap[fiu])
        fiu=(nod<<1)+1;
    if(fiu!=nod)
    {
        int aux;
        aux=heap[fiu];
        heap[fiu]=heap[nod];
        heap[nod]=aux;
        heap_down(fiu);
    }
}

void rez()
{
    int i,j,lim;
    long long s=0;
    for(i=1;i<=n;i++)
        if(v[i].t!=v[i+1].t)
        {
            heap[++nr]=v[i].x;
            heap_up(nr);
            lim=v[i].t-v[i+1].t;
            for(j=1;j<=lim && nr;j++)
            {
                s=s+heap[1];
                heap[1]=heap[nr];
                nr--;
                heap_down(1);
            }
        }
        else
        {
            heap[++nr]=v[i].x;
            heap_up(nr);
        }
    printf("%lld\n",s);
}

int main()
{
    read();
    sort(v+1,v+n+1,comp);
    rez();
    return 0;
}