Cod sursa(job #2453745)

Utilizator PaulOrasanPaul Orasan PaulOrasan Data 5 septembrie 2019 17:29:27
Problema Lupul Urias si Rau Scor 8
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>

using namespace std;

ifstream fin("lupu.in");
ofstream fout("lupu.out");

const int NMAX=100005;
int n,x,l,a[NMAX],t[NMAX];
int tmax;
int h[NMAX],indN;
void citire()
{
    fin>>n>>x>>l; int d;
    for (int i=1; i<=n; i++){
        fin>>d>>a[i];
        t[i]=1+(x-d)/l;
    }
}
void stabTMax()
{
    for (int i=1; i<=n; i++)
        if (t[i]>tmax)
            tmax=t[i];
}
void insertHeap(int i)
{
    indN++;
    int v=a[i],fiu=indN,tata=indN/2;
    while (tata && h[tata]<v){
        h[fiu]=tata;
        fiu=tata;
        tata/=2;
    }
    h[fiu]=v;
}
void combHeap(int i,int n)
{
    int v=h[i],tata=i,fiu=2*i;
    while (fiu<=n){
        if (fiu<n)
            if (h[fiu]<h[fiu+1])
                fiu++;
        if (h[fiu]>v){
            h[tata]=h[fiu];
            tata=fiu;
            fiu*=2;
        }else
            fiu=n+1;
    }
    h[tata]=v;
}
int extractHeap(int n)
{
    int v=h[1];
    h[1]=h[n];
    n--;
    combHeap(1,n);
    return v;
}
int rezolvare()
{
    int sol=0;
    for (int j=tmax; j>=1; j--){
        for (int k=1; k<=n; k++){
            if (t[k]==j)
                insertHeap(k);
        }
        sol+=extractHeap(indN);
    }
    return sol;
}
int main()
{
    citire();
    stabTMax();
    fout<<rezolvare();
}