2276 - Cb

Enunt

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ță

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

Ieșire

4
9
1
0
3
0
7

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line="1" start="1">

def validate_input(n, T, a, intervals):

   if len(a) != n:
       return False
   for x, y in intervals:
       if x > y:
           return False
   return True

def count_numbers_in_intervals(n, T, a, intervals):

   if not validate_input(n, T, a, intervals):
       return []

   counts = []
   for x, y in intervals:
       count = 0
       for num in a:
           if x <= num <= y:
               count += 1
       counts.append(count)

   return counts

if __name__ == '__main__':

   n, T = map(int, input().split())
   a = list(map(int, input().split()))

   intervals = []
   for i in range(T):
       x, y = map(int, input().split())
       intervals.append((x, y))

   counts = count_numbers_in_intervals(n, T, a, intervals)

   for count in counts:
       print(count)

</syntaxhighlight>