Galerie

Solutia 1 : Serban Andrei Stan

Pentru un query (X,Y) ne intereseaza numarul de cartite care vor traversa galeria curenta, mai exact numarul de intervale (P,Q) astfel incat P≤X si Y≤Q. Costul final se va imbunatati cu L_galerie * Nr_cartite. Cum un interval (A,B),A≥B, este echivalent cu un interval (A,B),A≤B, vom interschimba in primul caz pe A cu B.

Pentru a raspunde in mod eficient la fiecare intrebare o sa folosim un AIB. Initial, pentru fiecare vizita (P,Q),vom insera in AIB la pozitia P numarul de cartite care pleaca din P spre Q.
Vom parcurge query-urile in ordine dupa capatul din dreapta, si la fiecare pas vom elimina din aib pozitiile reprezentand vizite cu Q≤Y-1. Numarul de cartite care vor traversa intervalul (X,Y) va fi egal cu suma valorilor ce se afla in AIB pe pozitii ≤P.

Complexitatea finala va fi O(MlogM + TlogT + (M+T)logN).

Solutia 2 : Teodor Anton Pripoae

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.