Fişierul intrare/ieşire:intervale2.in, intervale2.outSursăCerc Nerdvana
AutorDin FolclorAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.3 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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 ≤ aibi ≤ 1 miliard

Exemplu

intervale2.inintervale2.outExplicaţ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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici