3972 - Wall

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 pe ecran numărul de subsecvențe ale șirului dat care respectă condiția din enunț.

Restricții și precizări

• 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

Exemplu:

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).

<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

1. Citirea datelor de intrare

N = int(input()) arr = list(map(int, input().split())) T = int(input())

1. Calcularea și afișarea rezultatului

result = num_subsequences_with_condition(arr, N, T) print(result) </syntaxhighlight>