Cod sursa(job #2067164)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 15 noiembrie 2017 22:46:16
Problema Lupul Urias si Rau Scor 84
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 1.6 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream  fin("lupu.in");
ofstream fout("lupu.out");
int n,x,l,i,t,h,dif;
long long s;
struct oaie
{
    int d,l;
};
oaie o[100009],aux;
void down(int k, int n);
void up(int k, int 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);
    o[n+1]={o[n].d+1,0};///santinela
    s=0;t=-1;h=0;///o[1..h] este heap-ul
    for(i=1;i<=n+1;i++){
        if(o[i].d>t){
            dif=o[i].d-t;
            while(h>0 && dif>0){
                s=s+o[1].l;
                o[1]=o[h];
                h--;
                down(1,h);
                dif--;
            }
            t=o[i].d;
        }
        h++;o[h]=o[i];
        up(h,h);
    }
    fout<<s;
    fin.close();
    fout.close();
    return 0;
}

void down(int k, int n)
{
    int 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(int k, int n)
{
    int 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;
    }
};