Cod sursa(job #967918)

Utilizator ScoobyDoo38Nita Adrian Valentin ScoobyDoo38 Data 28 iunie 2013 20:20:33
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.71 kb
#include <fstream>
#include <array>
#include <vector>
#include <functional>
#include <cstdlib>
#include <algorithm>

using namespace std;

template< class type1, int size, class type2 >
void quick3s( array< type1, size >& sort, array< type2, size >& nosort, const int begin, const int end )
{
	if ( end - begin < 2 )
		return;

	unsigned left = begin;
	unsigned right = end - 1;
	unsigned index = begin;

	type1 pivot = sort[ rand() % ( end - begin - 1 ) + begin ];

	while ( index <= right )
	{
		if		( sort[ index ] < pivot )
		{
			std::swap( nosort[ index ], nosort[ left ] );
			std::swap( sort[ index++ ], sort[ left++ ] );
		}
		else if ( sort[ index ] > pivot )
		{
			std::swap( nosort[ index ], nosort[ right ] );
			std::swap( sort[ index ], sort[ right-- ] );
		}
		else
			index++;
	}

	quick3s( sort, nosort, begin, left );
	quick3s( sort, nosort, right + 1, end );
}

template< class type, class comp >
inline void swim( vector< type >& heap, unsigned k, comp compare )
{
	while ( k > 1 && !compare( heap[ k / 2 ], heap[ k ] ) )
	{
		std::swap( heap[ k / 2 ], heap[ k ] );
		k /= 2;
	}
}

template< class type, class comp >
void sink( vector< type >& heap, unsigned k, comp compare )
{
	const unsigned n = heap.size();

	while ( 2 * k < n )
	{
		unsigned j = 2 * k;

		if ( j + 1 < n && compare( heap[ j + 1 ], heap[ j ] ) )
			j++;

		if ( compare( heap[ k ], heap[ j ] ) )
			break;
		else
			std::swap( heap[ k ], heap[ j ] );

		k = j;
	}
}

template< class type, class comp >
inline void insert( vector< type >& heap, type v, comp compare )
{
	heap.push_back( v );
	swim( heap, heap.size() - 1, compare );
}

template< class type, class comp >
inline type del( vector< type >& heap, comp compare )
{
	type ceva = heap[ 1 ];

	std::swap( heap[ 1 ], heap.back() );
	heap.pop_back();
	sink( heap, 1, compare );

	return ceva;
}

int main()
{
	ifstream in("lupu.in");
	ofstream out("lupu.out");

	int n = 0, x = 0, l = 0;

	in >> n >> x >> l;

	array< int, 100000 > dist;
	array< int, 100000 > lana;

	for ( int i = 0; i < n; i++ )
	{
		in >> dist[ i ];
		dist[ i ] = ( x - dist[ i ] ) / l;

		in >> lana[ i ];
	}
	in.close();

	srand( n );
	quick3s( dist, lana, 0, n );

	vector< int > heap;
	heap.push_back( 0 );

	vector< int > end;
	end.push_back( 0 );

	int index = 0;
	while ( dist[ index ] < 0 )
		index++;

	long long s = 0;
	for ( int i = n - 1; i >= index; i-- )
	{
		while ( i > index && dist[ i - 1 ] == dist[ i ] )
			insert( heap, lana[ i-- ], std::greater< int >() );

		insert( heap, lana[ i ], std::greater< int >() );
		s += del( heap, std::greater< int >() );
	}

	out << s;

	out.close();

	return 0;
}