==include(page="onis-2015/solutii-runda-1/invazia")==

Solutia corecta la aceasta problema presupune cunoasterea structurii de date 'Arbore de intervale': http://www.infoarena.ro/problema/arbint.
 
Problema se poate rezolva prin mentinerea in fiecarui nod al unui arbore de intervale o structura de date auxiliara care sa poata sa raspunda rapid la inserari, stergeri si query-uri de minim (de exemplu, heap). Insa, cum operatiile de inserare si stergere la problema aceasta erau parantezate corect, este indeajuns o stiva.
 
Cand primim o inserare, descompunem intervalul primit in cele logN noduri corespunzatoare din arborele de intervale, si incarcam in varful stivei din fiecare din aceste noduri min(inaltimea noii nave, varful precedent al stivei). La stergere, luam intervalul asociat ultimei inserari (care il vom memora probabil tot cu ajutorul unei stive) si, din nou, il descompunem in cele logN noduri asociate pe stivele carora apelam pop()(stergem varful).
 
De notat este ca problema nu necesita lazy-update, intrucat query-urile sunt punctiforme (nu sunt pe interval). Un query va parcurge pe arborele de intervale un drum de la radacina la o frunza. Daca in fiecare dintre nodurile de pe drum, ne uitam la ce se afla in varful stivei, raspunsul pentru query va fi minimul dintre aceste valori.
 
Complexitatea este <tex>O(M*logN)</tex>
 

==include(page="onis-2015/solutii-runda-1/livada")==

==include(page="onis-2015/solutii-runda-1/meciul")==
==include(page="onis-2015/solutii-runda-1/perechile")==