Editing 3872 - cnt seq max min (section)

== 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)
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()

</syntaxhighlight>