Cod sursă (job #495408)

#include <cstdio>
#include <algorithm>
#include <cstring>
#define Maxn 5000002
using namespace std;
int n, i, j, d, x, top, day, sum;
struct tulip
{
    int x;
    int y;
} st[Maxn];
void quicks(int b, int e)
{
    int i, j, piv;
    while (b < e)
    {
        i = b;
        j = e;
        piv = st[(b + e) / 2].x + day - st[(b + e) / 2].y;
        while (i <= j)
        {
            while (st[i].x + day - st[i].y < piv && i <= e)
                ++ i;
            while (st[j].x + day - st[j].y > piv && j >= b)
                -- j;
            if (i <= j)
                swap(st[i], st[j]),
                     ++ i,
                        -- j;
        }
        if (top / 2 + 1 >= i)
            b = i;
        else if (top / 2 + 1 <= j)
            e = j;
        else
            b = e = top / 2 + 1;
    }
}
int main()
{
    freopen("lalele.in", "r", stdin);
    freopen("lalele.out", "w", stdout);
    scanf("%d", &n);
    while (n)
    {
        scanf("%d %d", &d, &x);
        n -= d;
        for (i = 1; i <= d; ++ i)
            if (x)
            {
                st[++ top].x = x;
                st[top].y = i + sum;
            }
            else
            {
                day = i + sum;
                quicks(1, top);
                printf("%d\n", st[top / 2 + 1].x + day - st[top / 2 + 1].y);
                top = top / 2;
            }
        sum += d;
    }
    return 0;
}