Fişierul intrare/ieşire:distincte2.in, distincte2.outSursăInfoarena Monthly 2012, Runda 3
AutorMihai-Alexandru DusmanuAdăugată decezar305Mr. Noname cezar305
Timp execuţie pe test0.125 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Distincte2

Fiindca l-a prins jucandu-se pe telefon in timpul orei de Potiuni, profesorul Snape i-a dat lui Harry o tema suplimentara pentru ziua urmatoare. Fiind dat un sir A cu N numere naturale reprezentand codurile vrajilor efectuate de elevii de la Hogwarts in ultimele 24 de ore, Harry trebuie sa raspunda la M intrebari de genul : "Cate vraji distincte ce au codurile in intervalul [X,Y] au fost efectuate in ultima zi?". Fiind prea ocupat cu Ginny, el va roaga sa ii faceti un program care sa il ajute sa raspunda la toate intrebarile profesorului Snape.

Date de intrare

Fişierul de intrare distincte2.in va contine pe prima linie numerele naturale N si M reprezentand numarul de elemente din sir si respectiv numarul de intrebari. A 2-a linie a fisierului de intrare contine cele N elemente ale sirului. Urmatoarele M linii vor contine cate 2 numere X si Y (X ≤ Y) reprezentand inceputul si sfarsitul unui interval interogat.

Date de ieşire

Fişierul de ieşire distincte2.out va avea M linii. Pe linia i se va afla un singur numar natural semnificand raspunsul pentru a i-a intrebare.

Restricţii

  • 1 ≤ N ≤ 100 000
  • 1 ≤ M ≤ 100 000
  • 1 ≤ A[i] ≤ 1 000 000
  • 1 ≤ X ≤ Y ≤ 1 000 000 pentru fiecare query

Exemplu

distincte2.indistincte2.out
8 4
2 7 5 3 1 2 3 4
1 2
2 5
3 3
1 10
2
4
1
6
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content