Fişierul intrare/ieşire: | intervale2.in, intervale2.out | Sursă | Cerc Nerdvana |
Autor | Din Folclor | Adăugată de | |
Timp execuţie pe test | 0.3 sec | Limită de memorie | 16384 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Intervale2 (clasa a 6-a)
Fie un şir de numere ordonate crescător X = x1, x2, ..., xN. Ni se cere să aflăm răspunsul la Q întrebări de forma:
Câte numere din şirul X sunt mai mari sau egale cu ai şi mai mici sau egale cu bi?
Date de intrare
Fişierul de intrare intervale2.in conţine pe prima linie numărul N de elemente ale şirului X. Pe a doua linie vom avea N numere ordonate crescător, numerele şirului X. Pe următoarea linie va fi numărul Q de întrebări. Pe următoarele Q linii vom avea perechi de numere ai şi bi.
Date de ieşire
În fişierul de ieşire intervale2.out Veţi afişa Q numere. Pe prima linie veţi afişa răspunsul la prima întrebare (câte numere din X sunt între a1 şi b1, inclusiv a1 şi b1?). Pe a doua linie veţi afişa răspunsul la a doua întrebare, şi aşa mai departe.
Restricţii
- 1 ≤ N ≤ 100000
- 1 ≤ Q ≤ 50000
- 1 ≤ xi ≤ 1 miliard
- 1 ≤ ai ≤ bi ≤ 1 miliard
Exemplu
intervale2.in | intervale2.out | Explicaţii |
---|---|---|
8 2 2 6 6 6 9 10 10 4 3 7 3 5 6 11 2 10 | 3 0 6 8 | Şirul X are 8 numere. Urmează 4 întrebări: - Câte numere sunt în X între 3 şi 7? Sunt numerele 6 6 6, deci 3 numere. - Câte numere sunt în X între 3 şi 5? Nu avem nici un număr între 3 şi 5. - Câte numere sunt în X între 6 şi 11? Sunt numerele 6 6 6 9 10 10, deci 6 numere. - Câte numere sunt în X între 2 şi 10? Toate numerele din X sunt între doi şi 10, deci 8 numere. |