Fișierul intrare/ieșire | intervale2.in, intervale2.out | Sursă | Cerc Nerdvana |
---|---|---|---|
Autor | din folclor | Adăugată de | Cristian Frâncu • francu |
Timp de execuție pe test | 0.3 sec | Limită de memorie | 16384 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile 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. |