Cod sursa(job #1242752)

Utilizator horatiu11Ilie Ovidiu Horatiu horatiu11 Data 14 octombrie 2014 22:57:39
Problema Lupul Urias si Rau Scor 32
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 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 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);
    for(i=1;i<=n;++i)
    {
        insert(o[i].l);
        if(o[i].t!=o[i+1].t)
        {
            s+=H[1];
            if(K==1)K--,H[1]=0;
            else erase(1);
        }
    }
    printf("%lld\n",s);
    return 0;
}