Cod sursă (job #495323)

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 5000000 + 1;

int A[Nmax];

int N, nrLalele;

void quicksort( int l, int r, int k )
{
	int i = l, j = r, pivot = A[l + rand() % (r - l + 1)];

	do
	{
		while ( A[i] < pivot ) i++;
		while ( A[j] > pivot ) j--;

		if ( i <= j )
		{
			swap( A[i], A[j] );
			i++;
			j--;
		}

	} while ( i < j );

	if ( l < j && j >= k )
		quicksort( l, j, k );

	if ( i < r && i <= k )
		quicksort( i, r, k );
}

void sterge( int medianValue )
{
	int c = 0;

	for ( int i = 1; i <= nrLalele; ++i )
		if ( A[i] < medianValue )
			A[ ++c ] = A[i];

	nrLalele /= 2;

	while ( c < nrLalele )
		A[ ++c ] = medianValue;
}

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

	srand( time( NULL ) );
	ios_base::sync_with_stdio( false );

	in >> N;

	int d, x, crestere = 0;

	while ( in >> d >> x )
	{
		if ( x > 0 ) /// sadesc d lalele de inaltime x
		{
			while ( d-- )
			{
				A[ ++nrLalele ] = x - crestere;
				crestere++;
			}
		}
		else
		{
			for ( int k = 0; k < d; ++k )
			{
				for ( int i = 1; i <= nrLalele; ++i )
					A[i] += crestere;

				int median = 1 + nrLalele / 2;

				quicksort( 1, nrLalele, median );

				out << A[median] << "\n";

				sterge( A[median] );

				crestere = 1;
			}
		}
	}

	return 0;
}