Cod sursa(job #2067826)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 16 noiembrie 2017 21:07:17
Problema Lupul Urias si Rau Scor 84
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 1.58 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream  fin("lupu.in");
ofstream fout("lupu.out");
int n,x,L,i,t,h,dif, dist;
long long s;
struct oaie{
    int nivel,lana;
};
oaie o[100009],aux;
void down(int n);
void up(int n);
bool cmp(oaie a, oaie b){
    if(a.nivel<b.nivel)return 1;
    if(a.nivel==b.nivel && a.lana<b.lana)return 1;
    return 0;
}
int main(){
    fin>>n>>x>>L;
    for(i=1;i<=n;i=i+1){
        fin>>dist>>o[i].lana;
        o[i].nivel=x/L-(x-dist)/L;///am calculat nivelul pe baza dist, L si x
    }
    sort(o+1, o+1+n, cmp);///sortare dupa nivel
    ///o[n+1] este santinela
    o[n+1].nivel=o[n].nivel+1;
    o[n+1].lana=0;
    s=0;t=-1;h=0;///o[1..h] este heap-ul si initial este vid
    for(i=1;i<=n+1;i++){
        if(o[i].nivel>t){///am trecut la un nivel nou
            dif=o[i].nivel-t;///diferenta de niveluri
            while(h>0 && dif>0){
                s=s+o[1].lana;
                o[1]=o[h]; h--; dif--;
                down(h);
            }
            t=o[i].nivel;
        }
        h++;o[h]=o[i];
        up(h);
    }
    fout<<s;
    fin.close();
    fout.close();
    return 0;
}

void down(int n){
    int t,f;
    t=1; f=2*t;
    while(f<=n){
        if(f<n && 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=2*t;
        }
        else break;
    }
}
void up(int n){
    int t,f;
    f=n; t=f/2;
    while(t>0 && o[f].lana>o[t].lana){
        aux=o[f]; o[f]=o[t]; o[t]=aux;
        f=t; t=f/2;
    }
}