Cod sursa(job #998702)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 17 septembrie 2013 20:54:05
Problema Lupul Urias si Rau Scor 32
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("lupu.in");
ofstream g("lupu.out");
long long N,X,L;
struct Sheep{
long long time;
long long value;
};
Sheep Array[100002];
long long Dist[100002];
long long Poz[100002];
long long Heap[100002],Result,NHeap;
bool compare(Sheep a,Sheep b)
{
    return a.time>b.time;
}
void Swap(long long X, long long Y)
{
    swap(Heap[X],Heap[Y]);
    swap(Poz[Heap[X]],Poz[Heap[Y]]);
}
void Read()
{
    long long i;
    f>>N>>X>>L;
    for(i=1;i<=N;i++)
    {
         f>>Dist[i]>>Array[i].value;
         Array[i].time=(X-Dist[i])/L+1;
    }
    sort(Array+1,Array+N+1,compare);
}
void Percolate (long long X)
{
    long long Father=(X>>1);
    if (Father>0 && Array[Heap[X]].value>Array[Heap[Father]].value)
    {
        Swap (X,Father);
        Percolate (Father);
    }
}
void Sift(long long X)
{
    long long Son=(X<<1);
    if(Son+1<=NHeap && Array[Heap[Son+1]].value>Array[Heap[Son]].value)
      Son++;
    if(Son<=NHeap && Array[Heap[Son]].value>Array[Heap[X]].value)
        {
            Swap(Son,X);
            Sift(Son);
        }
}
void Insert(long long X)
{
    Heap[++NHeap]=X;
    Poz[X]=NHeap;
    Percolate(NHeap);
}
void Erase(long long K)
{
    Swap(K,NHeap);
    --NHeap;
    Sift(K);
}
void Solve()
{
    long long i;
    long long value=Array[1].time;
    for(i=1;i<=N;i++)
    {
        if(Array[i].time!=value)
        {
            if(NHeap)
            {
                 Result+=Array[Heap[1]].value*(value-Array[i].time);
                 Erase(1);
            }
            value=Array[i].time;

        }
        Insert(i);
    }
    if(NHeap)
        Result+=Array[Heap[1]].value*value;
}
int main()
{
    Read();
    Solve();
    g<<Result<<"\n";
    return 0;
}