Fișierul intrare/ieșire: intervale2.in, intervale2.out Sursă Cerc Nerdvana
Autor din folclor Adăugată de francuCristian Francu francu
Timp execuție pe test 0.3 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate normalnormalnormalnormalnormal

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 ≤ aibi ≤ 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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii