Cod sursă (job #258682)

#include <cstdio>

#include <algorithm>

using namespace std;

FILE *f, *g;

int n, days, l;

int flori;

struct lalea
{
    int h, d;
};

lalea lalele[5000001], aux;

bool cmp(lalea a, lalea b)
{
    int x = a.h + days - a.d;
    int y = b.h + days - b.d;

    return (x <= y ? true : false);
}

void plant()
{
    lalele[++ flori].d = days;

    lalele[flori].h = l;
}

void quickSort(int st, int dr)
{
    int i, j, mid;

    i = st;

    j = dr;

    mid = lalele[(st + dr) / 2].h + days - lalele[(st + dr) / 2].d;

    do
    {

        while(i <= j)
        {
            while((i < dr) && (lalele[i].h + days - lalele[i].d < mid))
                i ++;

            while((j > st) && (lalele[j].h + days - lalele[j].d > mid))
                j --;

            if(i <= j)
            {
                aux = lalele[i];

                lalele[i] = lalele[j];

                lalele[j] = aux;

                i ++;

                j --;
            }
        }
    }
    while(i <= j);

    if(st < j)
        quickSort(st, j);

    if(i < dr)
        quickSort(i, dr);
}

void targ()
{
    int mid;

    quickSort(1, flori);

    mid = flori / 2 + 1;

    fprintf(g, "%d\n", lalele[mid].h + days - lalele[mid].d);

    flori /= 2;
}

void solve()
{
    f = fopen("lalele.in", "r");

    int i, d, mid;

    fscanf(f, "%d", &n);

    g = fopen("lalele.out", "w");

    while(n != 0)
    {
        fscanf(f, "%d%d", &d, &l);

        n -= d;

        for(i = 1; i <= d; i ++)
        {
            days ++;

            if(l != 0)
                plant();


            else
                targ();
        }
    }

    fclose(f);
    fclose(g);
}

int main()
{
    solve();

    return 0;
}