Cod sursa(job #2067161)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 15 noiembrie 2017 22:38:07
Problema Lupul Urias si Rau Scor 84
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 1.69 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream  fin("lupu.in");
ofstream fout("lupu.out");
long long n,x,l,i,s,t,h,v;
struct oaie
{
    long long d,l;
};
oaie o[100009],aux;
void down(long long k, long long n);
void up(long long k, long long n);
bool cmp(oaie a, oaie b){
    if(a.d<b.d)return 1;
    return 0;
}
int main()
{
    fin>>n>>x>>l;
    for(i=1;i<=n;i=i+1)
    {
        fin>>o[i].d>>o[i].l;
        o[i].d=x/l-(x-o[i].d)/l;///nivel
    }
    sort(o+1, o+1+n, cmp);
    s=0;t=-1;h=0;
    for(i=1;i<=n;i++){
        if(o[i].d>t){
            int dif=-t+o[i].d;
            while(h>0 && dif>0){
                v=o[1].l;
                o[1]=o[h];
                h--;
                down(1,h);
                s=s+v;
                dif--;
            }
            t=o[i].d;
        }
        h++;o[h]=o[i];
        up(h,h);
    }
    if(h>0){
        v=o[1].l;
        o[1]=o[h];
        s=s+v;
    }
    fout<<s;
    fin.close();
    fout.close();
    return 0;
}

void down(long long k, long long n)
{
    long long t,f;
    t=k;
    f=2*k;
    while(f<=n)
    {
        if(f<n)
        {
            if(o[f].l<o[f+1].l)
            {
                f=f+1;
            }
        }
        if(o[t].l<o[f].l)
        {
            aux=o[t];
            o[t]=o[f];
            o[f]=aux;
            t=f;
            f=f*2;
        }
        else
        {
            f=n+1;
        }
    }
};
void up(long long k, long long n)
{
    long long t,f;
    t=k/2;
    f=k;
    while(t && o[f].l>o[t].l)
    {
        aux=o[f];
        o[f]=o[t];
        o[t]=aux;
        f=t;
        t=t/2;
    }
};