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

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)