| Fişierul intrare/ieşire: | bitcost.in, bitcost.out | Sursă | Algoritmiada 2016, Runda Finala, Juniori |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Eugenie Daniel Posdarascu •eudanip |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Bitcost
Se da un vector cu K numere intregi, al i-lea numar reprezentand costul celui de al i-lea nesemnificativ bit. Definim costul unui numar x ca fiind suma costurilor bitilor de 1 din configuratia binara a numarului x. De exemplu daca avem vectorul [3, -2, 7], costul numarului 6(110) este -2 + 7 = 5 iar costul numarului 3(011) este 3 - 2 = 1. Se dau M query-uri de tipul a, b: care este costul maxim al unui numar din intervalul [a,b]?
Date de intrare
Fişierul de intrare bitcost.in va contine pe prima linie 2 numere naturale K si M. Pe linia a doua vor fi K numere reprezentand costurile bitilor. Pe urmatoarele M linii se vor afla cate 2 numere a, b reprezentand query-urile.
Date de ieşire
Fişierul de ieşire bitcost.out va contine M linii, pe linia i aflandu-se raspunsul pentru query-ul i.
Restricţii
- 1 ≤ K ≤ 60
- 1 ≤ M ≤ 100.000
- 1 ≤ a ≤ b ≤ 2K - 1
- Costurile sunt numere intregi din intervalul [-1.000.000, +1.000.000]
Exemplu
| bitcost.in | bitcost.out |
|---|---|
| 3 2 3 -2 7 1 7 2 4 | 10 7 |
