Cod sursă (job #563552)

#include <fstream>
#include <algorithm>

#define NMAX 5000005

using namespace std;

ifstream f("lalele.in");
ofstream g("lalele.out");

int total_days, days, h, day, n, first;

struct Lalele{
    int day;
    int height;
};
Lalele v[NMAX];

void quickSelect(int n, int k, int left, int right)
{
    int pivot = right, poz = left;
    for(int i = left; i < right; i++)
    {
        if(v[i].height - v[i].day <= v[pivot].height - v[pivot].day)
        {
            Lalele temp = v[poz];
            v[poz] = v[i];
            v[i] = temp;
            poz++;
        }
    }

    Lalele temp = v[poz];
    v[poz] = v[pivot];
    v[pivot] = temp;

    if(poz < k)
        quickSelect(n, k, poz + 1, right);
    if(poz > k)
        quickSelect(n, k, left, poz - 1);
}

int main()
{
    f >> total_days;

    while(total_days)
    {
        f >> days >> h;

        if(h > 0)
        {
            while(days)
            {
                day++;
                v[++n].day = day;
                v[n].height = h;

                days--;
                total_days--;
            }
        }
        else
        {
            while(days)
            {
                day++;

                quickSelect(n, n / 2 + 1, 1, n);
                g << v[n / 2 + 1].height + day - v[n / 2 + 1].day << "\n";
                n = n / 2;

                days--;
                total_days--;
            }
        }
    }

    return 0;
}