Cod sursa(job #330711)

Utilizator jupanubv92Popescu Marius jupanubv92 Data 11 iulie 2009 12:31:21
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include<stdio.h>

#define MAX_N 100000+1
long long int n,nn,x,l,k;
long long int sol;
long long int A[MAX_N],Heap[MAX_N];
long long int T_MAX = -1;
long long int T[MAX_N];

void read(),solve(),heapUp(long long int),heapDown(long long int),heapDown2(long long int);
int main()
{
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);

	read();
	solve();
	printf("%lld\n",sol);

	fclose(stdin); fclose(stdout);
	return 0;
}

void read()
{
	long long int i;
	scanf("%lld%lld%lld",&n,&x,&l);
	T_MAX = x/l+1;
	for(i = 1; i <= n; i++)
	{
		scanf("%lld %lld",&T[i],&A[i]);
		if(T[i] <= x)
		{
		     T[i] = (x-T[i])/l+1;
		}
        else
        {
	         n--; i--;
        }
	}
	nn = n;
	for(i = nn/2; i >= 1; i--)
		heapDown2(i);

	while(nn > 2)
	{
		T[1] ^= T[nn] ^= T[1] ^= T[nn];
		A[1] ^= A[nn] ^= A[1] ^= A[nn];
		heapDown2(1);
		nn--;
	}
}


void solve()
{
	long long int i;
    long long int pos = n;
	for(i = T_MAX; i >= 1; i--)
	{
		while(T[pos] == i)
		{
			Heap[++k] = A[pos];
			heapUp(k);
			pos--;
		}
		if(k)
		{
			sol+= Heap[1];
			Heap[1] = Heap[k];
			Heap[k--]=0;
			heapDown(1);
		}
	}
}

void heapUp(long long int v)
{
	long long int key = Heap[v];
	while(v > 1 && key > Heap[v/2])
	{
		Heap[v/2] = Heap[v];
		v/=2;
	}
	Heap[v] = key;
}

void heapDown(long long int v)
{
	long long int w = v*2;
	while(w <= k)
	{
		if(w+1 <= k && Heap[w+1] > Heap[w]) w++;
		if(Heap[v] >= Heap[w]) return;

		Heap[w] ^= Heap[v] ^= Heap[w] ^= Heap[v];
		v = w;
		w *= 2;
	}
}

void heapDown2(long long int v)
{
	long long int w = v*2;
	while(w < nn)
	{
		if(w+1 < nn && T[w+1] > T[w]) w++;
		if(T[v] >= T[w]) return;

		T[w] ^= T[v] ^= T[w] ^= T[v];
		A[w] ^= A[v] ^= A[w] ^= A[v];
		v = w;
		w *= 2;
	}
}