Cod sursa(job #998568)

Utilizator mlupseLupse-Turpan Mircea mlupse Data 17 septembrie 2013 17:31:23
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("lupu.in");
ofstream g("lupu.out");
int N,X,L;
struct Sheep{
int time;
int value;
};
Sheep Array[100002];
int Dist[100002];
int Poz[100002];
int Heap[100002],Result,NHeap;
bool compare(Sheep a,Sheep b)
{
    return a.time>b.time;
}
void Swap(int X, int Y)
{
    swap(Heap[X],Heap[Y]);
    swap(Poz[Heap[X]],Poz[Heap[Y]]);
}
void Read()
{
    int i;
    f>>N>>X>>L;
    for(i=1;i<=N;i++)
    {
         f>>Dist[i]>>Array[i].value;
         Array[i].time=(X-Dist[i])/L;
    }
    sort(Array+1,Array+N+1,compare);
}
void Percolate (int X)
{
    int Father=(X>>1);
    if (Father>0 && Array[Heap[X]].value>Array[Heap[Father]].value)
    {
        Swap (X,Father);
        Percolate (Father);
    }
}
void Sift(int X)
{
    int 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(int X)
{
    Heap[++NHeap]=X;
    Poz[X]=NHeap;
    Percolate(NHeap);
}
void Erase(int K)
{
    Swap(K,NHeap);
    --NHeap;
    Sift(K);
}
void Solve()
{
    int i;
    int value=Array[1].time;
    for(i=1;i<=N;i++)
    {
        if(Array[i].time!=value)
        {
            value=Array[i].time;
            if(NHeap) Result+=Array[Heap[1]].value;
            Erase(1);
        }
        Insert(i);
    }
    if (NHeap) Result+=Array[Heap[1]].value;
}
int main()
{
    Read();
    Solve();
    g<<Result<<"\n";
    return 0;
}