Fișierul intrare/ieșire intervale2.in, intervale2.out Sursă Cerc Nerdvana
Autor din folclor Adăugată de avatar francu Cristian Frâncu • francu
Timp de execuție pe test 0.3 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.

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

Indicii de rezolvare

Arată 3 categorii