Cod sursa(job #2067259)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 16 noiembrie 2017 06:43:22
Problema Lupul Urias si Rau Scor 84
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 1.68 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 dist,lana;
};
oaie o[100009],aux;
void down(int k, int n);
void up(int k, int n);
bool cmp(oaie a, oaie b){
    if(a.dist<b.dist)return 1;
    return 0;
}
int main()
{
    fin>>n>>x>>l;
    for(i=1;i<=n;i=i+1)
    {
        fin>>o[i].dist>>o[i].lana;
        o[i].dist=x/l-(x-o[i].dist)/l;///am inlocuit distanta cu nivelul
    }
    sort(o+1, o+1+n, cmp);
    o[n+1]={o[n].dist+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].dist>t){
            dif=o[i].dist-t;
            while(h>0 && dif>0){
                s=s+o[1].lana;
                o[1]=o[h];
                h--;
                down(1,h);
                dif--;
            }
            t=o[i].dist;
        }
        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].lana<o[f+1].lana)
            {
                f=f+1;
            }
        }
        if(o[t].lana<o[f].lana)
        {
            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].lana>o[t].lana)
    {
        aux=o[f];
        o[f]=o[t];
        o[t]=aux;
        f=t;
        t=t/2;
    }
};