Cod sursă (job #417931)

#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;
}