Cod sursa(job #1702803)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 15 mai 2016 16:12:02
Problema Lupul Urias si Rau Scor 56
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <cstdio>
#include <algorithm>
#define file_size 3000000
using namespace std;

int N,X,L,d,Max=0,pos=1,Size=0,Heap[100001]={},P;
long long int S;
char file[file_size]={};
struct arr
{
	int t,val;
}v[100001];
bool cond(arr a, arr b)
{
	return a.t>b.t;
}
void r(int &nr)
{
	nr=0;
	while(file[P]<'0'||file[P]>'9')
		P++;
	while(file[P]>='0'&&file[P]<='9')
        nr=nr*10+file[P++]-'0';
}
void Read()
{
	 fread(file, 1, file_size, stdin);
	 r(N);r(X);r(L);
	  for(int i=1;i<=N;i++)
    {
       r(d);r(v[i].val);
        v[i].t=(X-d)/L+1;
        if(v[i].t>Max)
            Max=v[i].t;
    }
    sort(v+1,v+N+1,cond);
}
void Add_To_Heap(int element,int &Hl)
{
	Hl++;
	Heap[Hl]=element;
}
void Extract_From_Heap (int pos,int &Hl)
{
	int t=Heap[pos];
	Heap[pos]=Heap[Hl];
	Heap[Hl]=t;
	Hl--;
}
void Maxify_Heap(int pos,int Hl)
{
	int left=2*pos,right=2*pos+1,largest;
	if(left<=Hl&&Heap[left]>Heap[pos])
		largest=left;
	else
		largest=pos;
	if(right<=Hl&&Heap[right]>Heap[largest])
		largest=right;
	if(pos!=largest)
	{
		int t=Heap[largest];
		Heap[largest]=Heap[pos];
		Heap[pos]=t;
		 Maxify_Heap(largest,Hl);
	}
}
void Max_Heap (int Hl)
{
	for(int i=Hl/2;i>0;i--)
		Maxify_Heap(i,Hl);
}
int main()
{
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	Read();
	for(int i=Max;i>0;i--)
	{
		while(v[pos].t==i&&pos<=N)
		{
			Add_To_Heap(v[pos].val,Size);
			pos++;
		}
		if(Size>1)
		{
		Max_Heap(Size);
		S+=Heap[1];
		Extract_From_Heap(1,Size);
		Maxify_Heap(1,Size);
		}
		else if(Size==1)
		{
			S+=Heap[1];
			Size--;
		}
	}
	printf("%lld",S);
	return 0;
}