Cod sursa(job #1287882)

Utilizator Robert29FMI Tilica Robert Robert29 Data 8 decembrie 2014 10:24:56
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul II Marime 1.54 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
FILE*f=fopen("lupu.in","r");
FILE*g=fopen("lupu.out","w");
int nr,n,x,l;
long long sol;
struct oi
{
    int d,a;
}v[100001];
int cmp(oi a,oi b)
{
    return a.d<b.d;
}
int d[100001];
char viz[100001];
void insert(int x)
{
    d[++nr]=x;

    int k=nr;
    while(k>1&&d[k/2]<d[k])
    {
        d[0]=d[k];
        d[k]=d[k/2];
        d[k/2]=d[0];
        k/=2;
    }
}
void down(int x,int k)
{
    d[k]=d[nr--];
    int son;
    do
    {
        son=0;
        if(2*k<=nr)
            son=2*k;
        if(2*k+1<=nr&&d[son]<d[2*k+1])
            son++;
        if(d[son]>d[k])
        {
            d[0]=d[k];
            d[k]=d[son];
            d[son]=d[0];
            k=son;
        }
        else
            son=0;

    }while(son);

}
int main()
{
    fscanf(f,"%d%d%d",&n,&x,&l);
    for(int i=1;i<=n;++i)
        fscanf(f,"%d%d",&v[i].d,&v[i].a);

    sort(v+1,v+n+1,cmp);
    int max=0;
    int ok;
    for(int i=1;i<=n;++i)
    {
        ok=0;
        if(v[i].d<=x)
            ok=1;
        v[i].d=(x-v[i].d)/l;
        if(ok)
            ++v[i].d;
        if(v[i].d>max)
            max=v[i].d;
    }
    int j=1;
    for(int i=max;i&&j<=n;--i)
    {
        while(v[j].d==i)
        {
            insert(v[j].a);
            ++j;
        }
        if(nr)
        {
            sol+=d[1];
            down(v[j].a,1);
        }

    }

    fprintf(g,"%lld",sol);

    fclose(f);
    fclose(g);
    return 0;
}