Brianna Waltner: Pagină nouă: 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,...

2024-01-04T22:41:42Z

Pagină nouă: 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,...

New page

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 &les; n, T &les; 200 000'''
* '''0 &les; a[i] &les; 2 000 000 000'''
* '''0 &les; x &les; y &les; 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>

2276 - cb - Revision history