Cod sursa(job #1242759)

Utilizator horatiu11Ilie Ovidiu Horatiu horatiu11 Data 14 octombrie 2014 23:07:51
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
//horatiu11
# include <cstdio>
# include <cstring>
# include <algorithm>
# define nmax 100005
using namespace std;
long long n,x,l,H[nmax],d,Max,K,s;
struct oaie{long long l,t;}o[nmax];
inline bool cmp(oaie a, oaie b)
{return (a.t>b.t);}
inline long long father(long long k)
{return k/2;}
inline long long left_son(long long k)
{return k*2;}
inline long long right_son(long long k)
{return k*2+1;}
void sift(int k)
{
    long long son;
    do{
        son = 0;
        if (left_son(k)<=K)
        {
            son=left_son(k);
            if (right_son(k)<=K && H[right_son(k)]>H[left_son(k)])
                son=right_son(k);
            if (H[son]<=H[k])
                son=0;
        }
        if(son)
        {
            swap(H[k],H[son]);
            k=son;
        }
    }while(son);
}
void percolate(long long k)
{
    long long key=H[k];
    while(k>1 && key>H[father(k)])
    {
        H[k]=H[father(k)];
        k=father(k);
    }
    H[k]=key;
}
void erase(long long k)
{
    H[k]=H[K];
    --K;
    if ((k > 1) && (H[k] > H[father(k)]))
        percolate(k);
    else
        sift(k);
}
void insert(long long x)
{
    H[++K]=x;
    percolate(K);
}
int main()
{
    long long t,i;
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);
    scanf("%lld%lld%lld",&n,&x,&l);
    for(i=1;i<=n;++i)
    {
        scanf("%lld%lld",&d,&o[i].l);
        if(d<=x)o[i].t=(x-d)/l+1;
    }
    sort(o+1,o+n+1,cmp);
    i=1;
    for(t=o[i].t;t>0;--t)
    {
        while(i<n && o[i].t==t)
        {
            insert(o[i].l);
            ++i;
        }
        if(K>0)
        {
            s+=H[1];
            erase(1);
        }
        else if(i<n)
            t=o[i].t+1;
    }
    printf("%lld\n",s);
    return 0;
}