==include(page="dot-com/2009/solutii/runda-1/galerie")==

**Solutia 1 : Teodor Anton Pripoae**
 
Pentru inceput, vom observa ca nu conteaza cate cartite sunt initial intr-o camera.
 
Vom calcula pentru fiecare intrebare a organizatorilor, cate drumuri ale cartitelor contin acel interval (sa zicem Nr). Costul imbunatatirii va fi Nr * (lungime_interval - cost_interval). Pe exemplul din enunt unde merg 2 cartite intre camerele 1 si 4, vor exista 2 drumuri care contin intervalul [1, 3] : Drumul facut de prima cartita, respectiv a doua cartita din camera 1 pana in camera 4.
 
Acum, trebuie sa vedem cum putem raspunde eficient la intrebarea: Cate drumuri contin un interval cautat de organizatori. Vom retine intervalele ca puncte in plan (atat drumurile cat si intrebarile), coordonata x va fi capatul din stanga, iar coordonata y capatul din dreapta. Pentru ca un interval sa fie cuprins de altul, trebuie ca primul punct sa fie in stanga si deasupra celul de-al doilea. Vom sorta crescator toate cele M + T puncte dupa coordonata x si in caz de egalitate descrescator dupa coordonata y. Acum, pt fiecare punct (interval) cautat, raspunsul va fi numarul de puncte cu aflate inaintea lui in vector care au coordonata y mai mare decat a lui.
 
Vom proceda ca la subsir descrescator maximal. Vom tine un aib (Arbore indexat binar). La pasul i, vom vedea daca punctul curent(P) este din cele M, caz in care vom updata pe pozitia corespunzatoare coordonatei P.y in aib numarul de cartite care trec pe acel interval, sau in caz ca este din cele T vom vedea cu ajutorul aib-ului cate drumuri a caror coordonate R.y sunt mai mari decat coordonata P.y a lui: scadem din suma totala, suma pozitiilor pana la P.y - 1.
 
Solutia are complexitate o((M + T) (log (M + T) + log N)) ca timp si o(N) ca memorie.
 
 

==include(page="dot-com/2009/solutii/runda-1/trilant")==