Cod sursă (job #495669)

#include <bits/stdc++.h>
using namespace std;

int A[5000001];
int N, nrLalele;
int d,x,crestere=0;

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");

    in>>N;

    while (in>>d>>x){
        if (x>0){
            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;
}