Fişierul intrare/ieşire:bitcost.in, bitcost.outSursăAlgoritmiada 2016, Runda Finala, Juniori
AutorEugenie Daniel PosdarascuAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test0.4 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inbitcost.out
3 2
3 -2 7
1 7
2 4
10
7
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?