Fişierul intrare/ieşire:cuburi2.in, cuburi2.outSursăStelele Informaticii 2009, clasele 9-10
AutorPaul-Dan BaltescuAdăugată depauldbPaul-Dan Baltescu pauldb
Timp execuţie pe test0.75 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.incuburi2.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content