== include(page="template/taskheader" task_id="cuburi2") ==
Poveste şi cerinţă...
Laura si Robert se joaca cu cuburile. Robert a construit $N$ turnuri in linie dreapta si stie inaltimea fiecaruia. Pentru a muta un cub dintr-un turn in turnul vecin costa o unitate de timp. Acum, el ii pune $M$ intrebari Laurei in felul urmator: _"Care este timpul minim necesar pentru a muta toate cuburile din intervalul $x y$ intr-un singur turn deja existent?"_ Desigur, pe el il intereseaza si care va fi turnul destinatie ales in cazul unei astfel de intrebari. Laura ar putea raspunde cu usurinta la aceste intrebari folosindu-si intuitia feminina, dar s-a decis sa o pastreze pentru alte ocazii. Asadar, va trebui ca voi sa raspundeti la intrebarile lui Robert.
h2. Date de intrare
Fişierul de intrare $cuburi2.in$ ...
Pe prima linie a fisierului de intrare $cuburi2.in$ se afla numerele $N$ si $M$. Pe urmatoarea linie se afla $N$ numere, semnificand inaltimea turnurilor. Urmatoarele $M$ linii contin cate doua numere $x y$, fiecare pereche reprezinta o intrebare pusa de Robert.
h2. Date de ieşire
În fişierul de ieşire $cuburi2.out$ ...
In fisierul de iesire $cuburi2.out$ se vor afla $M$ linii, pe fiecare linie aflandu-se raspunsul la cate o intrebare pusa de Robert. Ordinea raspunsurilor trebuie sa coincida cu ordinea in care sunt puse intrebarile. Raspunsurile vor fi afisate sub forma $P Cost$, unde $P$ reprezinta pozitia turnului destinatie pentru intrebarea respectiva, iar $Cost$ timpul minim necesar pentru a muta toate cuburile in acest turn.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 250 000$
* $1 ≤ M ≤ 250 000$
* Inaltimile turnurilor sunt numere intregi cuprinse in intervalul $[0, 1 000 000]$.
* Pentru $20%$ din teste $N, M ≤ 250$
* Pentru $50%$ din teste $N, M ≤ 5 000$
* Se acorda $40%$ din punctaj daca determinati doar pozitia finala corect pentru toate intrebarile. Totusi, in acest caz va trebui sa afisati o valoare si pentru timpul minim, chiar daca nu corecta, pentru a respecta formatul datelor de iesire.
* Daca exista mai multe pozitii optime pentru turnul destinatie, oricare va fi considerata corecta.
h2. Exemplu
table(example). |_. cuburi2.in |_. cuburi2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 4
1 3 7 2 5
1 5
1 3
3 5
1 2
| 3 17
3 5
4 12
2 1
|
h3. Explicaţie
...
Pentru prima intrebare, turnul destinatie se afla la pozitia $3$. Timpul necesar pentru a muta restul cuburilor pe aceasta pozitie este $2*1 + 1*3 + 1*2 + 5*2 = 17$. Pentru a treia intrebare o alta pozitie finala posibila este $3$, care da acelasi timp minim $12$.
== include(page="template/taskfooter" task_id="cuburi2") ==
