2276 - cb

Se consideră un șir a[1], a[2], …, a[n] de numere naturale. Se dau și T intervale închise de forma [x, y], cu x ≤ y.

Cerinţa

Pentru fiecare din cele T intervale de forma [x, y] trebuie să răspundeți la întrebarea: câte numere din șir aparțin intervalului [x, y]?

Date de intrare

Programul citește de la tastatură numerele n și T, apoi n numere naturale, separate prin spații, a[1], a[2], …, a[n]. Pe următoarele T linii se află câte două numere naturale x și y reprezentând un interval [x, y].

Date de ieșire

Programul va afișa pe ecran T linii. Pe fiecare linie i (i=1..T) se va afla un singur număr natural reprezentând răspunsul la a i-a întrebare.

Restricţii şi precizări

• 1 ⩽ n, T ⩽ 200 000
• 0 ⩽ a[i] ⩽ 2 000 000 000
• 0 ⩽ x ⩽ y ⩽ 2 000 000 000

Exemplul 1

Intrare

9 7
6 1 3 5 3 3 9 20 9
4 10
0 100
0 1
500 506
3 3
10 18
3 9

Iesire

Datele de intrare corespund restrictiilor impuse
4
9
1
0
3
0
7

Exemplul 2

Intrare

210000 5
16 17 20 24 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105
4 10
0 100
0 1
500 506
3 3
10 18
3 9

Iesire

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python" line> from bisect import bisect_left, bisect_right

n, T = map(int, input().strip().split()) if not (1 <= n <= 200000 and 1 <= T <= 200000):

   print("Datele de intrare nu corespund restrictiilor impuse")
   exit(1)

students = sorted(list(map(int, input().split()))) if any(s < 0 or s > 2000000000 for s in students):

   print("Datele de intrare nu corespund restrictiilor impuse")
   exit(1)

intervals = [list(map(int, input().split())) for _ in range(T)] if any(x < 0 or y < x or y > 2000000000 for x, y in intervals):

   print("Datele de intrare nu corespund restrictiilor impuse")
   exit(1)

print("Datele de intrare corespund restrictiilor impuse")

for x, y in intervals:

   start = bisect_left(students, x)
   end = bisect_right(students, y)
   print(end - start)

</syntaxhighlight>