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ț. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

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

Ieșire

8

Explicație

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

Exemplul 2:

Intrare

123213123 323

Ieșire

Datele nu corespund restrictiilor impuse

Rezolvare

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)
from collections import deque

def check_restrictions(n, t, v):
    if not (1 <= n <= 1000000):
        return False
    if not (0 <= t <= 2000000000):
        return False
    for num in v:
        if not (-1000000000 <= num <= 1000000000):
            return False
    return True

def solve(n, t, v):
    st = dr = 0
    mini = deque()
    maxi = deque()
    ans = 0

    for i in range(n):
        while mini and v[i] < v[mini[-1]]:
            mini.pop()
        
        while maxi and v[i] > v[maxi[-1]]:
            maxi.pop()
        
        mini.append(i)
        maxi.append(i)

        if maxi and mini and v[maxi[0]] - v[mini[0]] <= t:
            ans += dr - st + 1
        else:
            while maxi and mini and v[maxi[0]] - v[mini[0]] > t:
                if maxi[0] == st:
                    maxi.popleft()
                
                if mini[0] == st:
                    mini.popleft()
                
                st += 1
            
            if maxi and mini:
                ans += dr - st + 1
        
        dr += 1
    
    print(ans)

def main():
    n, t = map(int, input().split())
    
    if not (1 <= n <= 1000000) or not (0 <= t <= 2000000000):
        print("Datele nu corespund restrictiilor impuse")
        return
    
    v = [int(x) for x in input().split()]

    if not check_restrictions(n, t, v):
        print("Datele nu corespund restrictiilor impuse")
        return
    
    solve(n, t, v)

main()