Màxim en Finestra W37576

Donada una seqüència de $N$ enters i una mida de finestra $W$, per a cada posició $i$ de la seqüència cal trobar el màxim de la finestra que acaba a $i$. La finestra conté els elements des de la posició $\max(0, i - W + 1)$ fins a $i$ (ambdós inclosos).

Per resoldre aquest problema de manera eficient, farem servir una cua de prioritat (en el nostre cas, un max-heap) que emmagatzema parelles (valor, índex). Definim l’struct:

struct Elem {
    int valor;
    int index;
};

amb la comparació:

bool operator>(const Elem& a, const Elem& b) {
    return a.valor > b.valor;
}

La tècnica per poder fer això de forma eficient és la següent. Per a cada nou element de la seqüència, el fiquem a la cua de prioritat. Després, mentre l’element del cim tingui un índex fora de la finestra (és a dir, index <= i - W), el traiem. El màxim actual de la finestra serà, doncs, el valor del cim de la cua de prioritat.

Aquesta tècnica s’anomena “esborrat mandrós” (lazy deletion): els elements que ja no pertanyen a la finestra no s’eliminen immediatament, sinó que es treuen només quan arriben al cim del heap. Això fa que l’algorisme sigui molt eficient en la pràctica.

Entrada

La primera línia conté un enter $W$ ($W \geq 1$), la mida de la finestra. A continuació, una seqüència d’enters separats per espais fins al final de l’entrada.

Sortida

Per a cada posició de la seqüència (començant per la primera), el màxim de la finestra corresponent, un per línia.

Observació

Aquest és un problema d’eficiència. Una solució ingènua que recorri tota la finestra per a cada posició no passarà els casos de prova grans, però la solució amb una cua de prioritat sí.

Has d’enviar un fitxer program.cc que inclogui "heap.hh". Als fitxers públics trobaràs heap.hh i assert.hh.