| 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 reprezinta 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. 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.
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.
Exemplu
| cuburi2.in | cuburi2.out |
|---|---|
| 5 4 1 3 7 2 5 1 5 1 3 3 5 1 2 | 3 17 3 5 4 12 2 1 |
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.
