Cod sursa(job #970648)

Utilizator ScoobyDoo38Nita Adrian Valentin ScoobyDoo38 Data 7 iulie 2013 15:02:37
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <fstream>
#include <array>
#include <vector>
#include <functional>
#include <cstdlib>
#include <algorithm>

using namespace std;

void quick3s( array< int, 100000 >& sort, array< unsigned, 100000 >& nosort, const int begin, const int end )
{
	if ( end - begin < 2 )
		return;

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

	int 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< unsigned, 100000 > lana;

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

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

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

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

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

        if ( heap.size() > 1 )
            s += del( heap, std::greater< int >() );
	}

	out << s;

	out.close();

	return 0;
}