Cod sursă (job #95243)

/* Desi solutia pare a fi O(n^2), aceasta este, de fapt, O(n) amortizat, 
deoarece fiecare floare este plantata o data si taiata o data, iar
quickselect-ul, fiind liniar, adauga la complexitate O(N/2 + N/4 + ...) = O(n)*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX 5000000
int v[MAX + 1];

void init()
{
	srand(time(NULL));
}

int qselect(int b, int e, int k) { // Observam ca functia de quick-select lasa elementele mai mari ca medianul in partea dreapta
	if (e - b > 1) { // Daca vectorul are mai mult de un element
		int piv = v[b + rand() % (e - b)];
		int left = b - 1, right = e;
		while (left < right) {
			while (v[++left] < piv);
			while (v[--right] > piv);
			if (left < right) {
				int aux = v[left];
				v[left] = v[right];
				v[right] = aux;
			}
		}
		int ln = (k < left ? b : left), rn = (k < left ? left : e);
		qselect(ln, rn, k);
	} else {
		return b; // Ne intereseaza locul in vector, nu valoarea
	}
}

int main()
{
	FILE *fin, *fout;
	fin = fopen("lalele.in", "r");
	fout = fopen("lalele.out", "w");

	init();

	// Citire
	int N, c = 0, size = 0; // c este contorul, iar size este marimea
	fscanf(fin, "%d", &N);
	while (c < N) {
		int d, x;
		int j;
		fscanf(fin, "%d%d", &d, &x);

		if (x) { // Daca este o zi normala de plantat
			c += d;
			for (j = 1; j <= d; j++) { // In loc sa adaugam 1 la fiecare floare zilnic, le lasam pe toate in pace, si scadem doar pe cea curenta
				size++;
				v[size] = j - c + x; // putem rescrie peste vechile valori, deoarece nu ne mai trebuie
			}
		} else { // Daca e zi de targ
			for (j = 1; j <= d; j++) {
				int poz = qselect(1, size + 1, size / 2 + 1);
				size = poz - 1;
				fprintf(fout, "%d\n", v[poz] + (c++)); // Avem grija sa readaugam zilele pierdute la numarare
			}
		}
	}

	fclose(fin);
	fclose(fout);
	return 0;
}