Pagini recente » Cod sursa (job #655730) | Cod sursa (job #431895) | Cod sursa (job #1843097) | Cod sursa (job #2880126) | Cod sursa (job #780243)
Cod sursa(job #780243)
#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;
}