Cod sursa(job #1242741)

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