Cod sursa(job #780243)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 20 august 2012 02:47:19
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb

#include <cstdio>

const unsigned int MAX_SIZE(100002);

unsigned int start [MAX_SIZE];
unsigned int end [MAX_SIZE];
unsigned int best_time [MAX_SIZE];

inline void swap (const unsigned int a, const unsigned int b)
{
	start[a] ^= start[b];
	start[b] ^= start[a];
	start[a] ^= start[b];
	end[a] ^= end[b];
	end[b] ^= end[a];
	end[a] ^= end[b];
}

inline void heap_down (unsigned int index, const unsigned int n)
{
	unsigned int left((index << 1) + 1), right(left + 1), largest;
	while (true)
	{
		if (left < n && end[left] > end[index])
			largest = left;
		else
			largest = index;
		if (right < n && end[right] > end[largest])
			largest = right;
		if (largest == index)
			break;
		swap(index,largest);
		index = largest;
		left = (index << 1) + 1;
		right = left + 1;
	}
}

inline void build_heap (const unsigned int n)
{
	for (signed int index((n >> 1) - 1) ; index >= 0 ; --index)
		heap_down(index,n);
}

inline void heap_sort (const unsigned int n)
{
	build_heap(n);
	for (unsigned int index(n - 1) ; index > 0 ; --index)
	{
		swap(0,index);
		heap_down(0,index);
	}
}

int main (void)
{
	std::freopen("heavymetal.in","r",stdin);
	std::freopen("heavymetal.out","w",stdout);
	unsigned int n;
	std::scanf("%u",&n);
	unsigned int *start_iterator(start), *start_last(start + n), *end_iterator(end);
	do
	{
		std::scanf("%u%u",start_iterator,end_iterator);
		++end_iterator;
		++start_iterator;
	}
	while (start_iterator < start_last);
	std::fclose(stdin);
	heap_sort(n);
	start_iterator = start;
	end_iterator = end;
	unsigned int last_concert(end[n - 1]), last_time(0), i(2), concert_start, concert_end, time;
	do
	{
		best_time[i] = last_time;
		if (*end_iterator == i)
		{
			concert_end = *end_iterator;
			do
			{
				concert_start = *start_iterator;
				time = best_time[concert_start] + concert_end - concert_start;
				if (best_time[i] < time)
					best_time[i] = time;
				++start_iterator;
				++end_iterator;
				concert_end = *end_iterator;
			}
			while (concert_end == i);
			last_time = best_time[i];
		}
		++i;
	}
	while (i <= last_concert);
	std::printf("%u\n",best_time[last_concert]);
	std::fclose(stdout);
	return 0;
}