3872 - cnt seq max min

Cerinta

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 iesire

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

Restrictii si precizari

• 1 ≤ N ≤ 1.000.000

• 0 ≤ T ≤ 2.000.000.000

• cele N numere citite vor fi din intervalul [-1.000.000.000, 1.000.000.000]

• 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 30 de puncte N ≤ 10.000

• pentru teste în valoare de 70 de puncte N ≤ 600.000

Exemplul 1

intrare

5 2

1 7 2 3 4

iesire

Datele introduse corespund restrictiilor impuse

8

Exemplul 2

intrare

-1 0

34 63 97 83 21

iesire

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

<syntaxhighlight lang="python3" line="1">

def numar_subsecvente(arr, T):

   n = len(arr)
   rezultat = 0
   
   # Sortăm șirul pentru a face procesul mai eficient
   arr.sort()

   # Folosim doi pointeri pentru a găsi subsecvențele
   stanga = 0
   dreapta = 0

   while stanga < n:
       while dreapta < n and arr[dreapta] - arr[stanga] <= T:
           dreapta += 1

       # Numărul de subsecvențe care încep cu stanga și au dreapta ca ultim element
       rezultat += dreapta - stanga

       # Ne deplasăm spre următorul element
       stanga += 1

   return rezultat

print("Numărul de subsecvențe este:", rezultat)

</syntaxhighlight>