Cod sursă (job #258683)

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

    while(st < dr)
    {
        i = st;

        j = dr;

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

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

        if (flori / 2 + 1 >= i)
            st = i;

        else if (flori / 2 + 1 <= j)
            dr = j;

        else
            st = dr = flori / 2 + 1;
    }
}

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