| Fişierul intrare/ieşire: | copii3.in, copii3.out | Sursă | Algoritmiada 2018 Runda Maraton |
| Autor | Alexandru Petrescu, Andrei Popa, Mihai Calancea, Tamio-Vesa Nakajima | Adăugată de |  Alexandru Petrescu •alexpetrescu |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | copii3.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.
