RaulOtet: Pagină nouă: = Cerința = Se dă un șir de `N` numere întregi. Să se afle numărul de subsecvențe ale șirului pentru care diferența dintre elementul lor de valoare maximă și cel de valoare minimă este mai mică sau egală decât un număr întreg `T` dat. = Date de intrare = Programul citește de la tastatură numerele `N` și `T`, iar apoi `N` numere întregi, separate prin spații. = Date de ieșire = Programul va afișa...

2024-07-31T05:48:51Z

Pagină nouă: = Cerința = Se dă un șir de <code>N</code> numere întregi. Să se afle numărul de subsecvențe ale șirului pentru care diferența dintre elementul lor de valoare maximă și cel de valoare minimă este mai mică sau egală decât un număr întreg <code>T</code> dat. = Date de intrare = Programul citește de la tastatură numerele <code>N</code> și <code>T</code>, iar apoi <code>N</code> numere întregi, separate prin spații. = Date de ieșire = Programul va afișa...

New page

= Cerința =
Se dă un șir de <code>N</code> numere întregi. Să se afle numărul de subsecvențe ale șirului pentru care diferența dintre elementul lor de valoare maximă și cel de valoare minimă este mai mică sau egală decât un număr întreg <code>T</code> dat.

= Date de intrare =
Programul citește de la tastatură numerele <code>N</code> și <code>T</code>, iar apoi <code>N</code> numere întregi, separate prin spații.

= Date de ieșire =
Programul va afișa pe ecran numărul de subsecvențe ale șirului dat care respectă condiția din enunț.

= Restricții și precizări =

* <code>1 ≤ N ≤ 1.000.000</code>
* <code>0 ≤ T ≤ 2.000.000.000</code>
* cele <code>N</code> numere citite vor fi din intervalul <code>[-1.000.000.000, 1.000.000.000]</code>
* se numește subsecvență a unui șir o succesiune de elemente consecutive din acesta, considerate în ordinea în care apar în șir
* pentru teste în valoare de <code>30</code> de puncte <code>N ≤ 10.000</code>
* pentru teste în valoare de <code>70</code> de puncte <code>N ≤ 600.000</code>

= Exemplu: =
'''Intrare'''
5 2
1 7 2 3 4
'''Ieșire'''
8

=== Explicație ===
Cele <code>8</code> subsecvențe care respectă condiția din enunț sunt toate cele <code>5</code> care conțin un singur element(diferența dintre elementul maxim și cel minim fiind astfel <code>0</code>), respectiv cele delimitate de perechile de indecși <code>[3, 4], [3, 5], [4, 5]</code>(șirul se consideră a fi indexat de la <code>1</code>).

<syntaxhighlight lang="python" line="1">
from collections import deque

def num_subsequences_with_condition(arr, N, T):
min_deque = deque()
max_deque = deque()
start = 0
count = 0

for end in range(N):
while min_deque and arr[min_deque[-1]] >= arr[end]:
min_deque.pop()
while max_deque and arr[max_deque[-1]] <= arr[end]:
max_deque.pop()

min_deque.append(end)
max_deque.append(end)

while arr[max_deque[0]] - arr[min_deque[0]] > T:
start += 1
if min_deque[0] < start:
min_deque.popleft()
if max_deque[0] < start:
max_deque.popleft()

count += (end - start + 1)

return count

# Citirea datelor de intrare
N = int(input())
arr = list(map(int, input().split()))
T = int(input())

# Calcularea și afișarea rezultatului
result = num_subsequences_with_condition(arr, N, T)
print(result)
</syntaxhighlight>

3972 - Wall - Revision history