Fişierul intrare/ieşire: | distincte2.in, distincte2.out | Sursă | Infoarena Monthly 2012, Runda 3 |
Autor | Mihai-Alexandru Dusmanu | Adăugată de | |
Timp execuţie pe test | 0.125 sec | Limită de memorie | 20480 kbytes |
Scorul tău | N/A | Dificultate | N/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.in | distincte2.out |
---|---|
8 4 2 7 5 3 1 2 3 4 1 2 2 5 3 3 1 10 | 2 4 1 6 |