Fişierul intrare/ieşire:copii3.in, copii3.outSursăAlgoritmiada 2018 Runda Maraton
AutorAlexandru Petrescu, Andrei Popa, Mihai Calancea, Tamio-Vesa NakajimaAdăugată dealexpetrescuPetrescu Alexandru alexpetrescu
Timp execuţie pe test1 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Copii3

Marcel este mare regizor. In fata lui sunt aliniate de la 1 la N niste scaune. Pe cateva dintre aceste scaune sunt asezati copii (personaje figurante intr-un film de al sau), cel mult un copil pe fiecare scaun.
Lenes din fire, Marcel s-a gandit ca i-ar sta bine sa se tolaneasca pe intervalul [L, R] de scaune. Pentru a face acest lucru, va trebui sa indeparteze copii din acel interval de scaune. Astfel, fiecare copil din intervalul [L, R] se va muta pe un scaun gol din afara intervalului. Marcel va trebui sa plateasca fiecarui copil mutat o prima de salariu egala cu distanta parcursa (adica diferenta in valoare absoluta dintre indicii scaunelor de pornire si oprire). Bineinteles, Marcel ar vrea sa plateasca cat mai putin per total.
Cum Marcel (persoana ingenioasa) doreste sa isi aleaga repede cel mai bun loc de tolanire, va da mai multe queryuri independente [L, R]. Pentru fiecare, gasiti cantitatea minima pe care Marcel o poate plati, sau determinati daca Marcel nu se poate tolani pe intervalul dat.

Date de intrare

Fişierul de intrare copii3.in contine pe prima linie numerele N si Q (numarul de queryuri).
Pe a doua linie, un sir de N caractere 0 sau 1; al i-lea caracter este 1 daca si numai daca pe al i-lea scaun sta un copil.
Pe urmatoarele Q linii vor urma cate doua numere L si R, reprezentand capetele unei interogari de a lui Marcel.

Date de ieşire

În fişierul de ieşire copii3.out se vor afla Q linii, pe a i-a linie fiind raspunsul la cel de-al i-lea query. Raspunsul la un query in care Marcel nu se poate aseza pe intervalul dat se considera a fi -1.

Restricţii si Punctare

  • Toate numerele din fisierul de intrare sunt naturale
  • Subtask 1 (feedback testul 3) - 20 de puncte: 1 ≤ N, Q ≤ 1.000
  • Subtask 2 (feedback testul 7) - 20 de puncte: 1 ≤ N ≤ 40.000; 1 ≤ Q ≤ 20.000
  • Subtask 3 (feedback testul 9) - 20 de puncte: 1 ≤ N ≤ 80.000; 1 ≤ Q ≤ 20.000
  • Subtask 4 (feedback testul 16) - 20 de puncte: 1 ≤ N, Q ≤ 80.000
  • Subtask 5 (feedback testul 17) - 20 de puncte: 1 ≤ N ≤ 320.000; 1 ≤ Q ≤ 80.000

Exemplu

copii3.incopii3.out
12 3
011101111000
6 9
7 12
1 5
10
-1
24
12 10
001011101000
1 7
2 8
3 9
4 10
5 11
6 12
10 12
5 7
5 9
5 12
20
17
16
15
14
15
0
6
10
-1

Explicaţie

Sa consideram primul exemplu. Notam cu litere mari copiii si avem sirul 0ABC0DEFG000.
Primul query: Dorim sa eliberam scaunele pe care stau D, E, F si G. D merge o pozitie la stanga, iar E, F si G cate 3 pozitii la dreapta. Efortul este 1 + 3 + 3 + 3 = 10.
Al doilea query: Dorim sa eliberam mai multe scaune decat e posibil. Prin urmare, nu se poate realiza obiectul, deci se afiseaza "-1".
Al treilea query: Dorim sa eliberam primele 5 scaune. Sirul final obtinut va fi 00000ABCDEFG, sau 00000DEFGABC, sau 00000DEFGCBA, etc, toate obtinand costul 24.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?