Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | cuburi2.in, cuburi2.out | Sursă | Stelele Informaticii 2009, clasele 9-10 |
| Autor | Paul-Dan Baltescu | Adăugată de |  Paul-Dan Baltescu •pauldb |
| Timp execuţie pe test | 0.375 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Cuburi2
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.
Date de intrare
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 reprezentand o intrebare pusa de Robert.
Date de ieşire
In fisierul de iesire cuburi2.out se vor afla M linii, pe fiecare linie aflandu-se raspunsul la cate o intrebare pusa de Robert. 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 intr-un singur turn.
Restricţii
- 1 ≤ N ≤ 250 000
- 1 ≤ M ≤ 250 000
- Pentru
Exemplu
| cuburi2.in | cuburi2.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
