# PBinfo #3872 – cnt_seq_max_min – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int MAXN = 1e4;
int a[1 + MAXN];
void max_self(int &x, const int &y) {
  if (x < y)
    x = y;
}
void min_self(int &x, const int &y) {
  if (x > y)
    x = y;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, t;
  cin >> n >> t;
  for (int i = 1; i <= n; ++i) 
    cin >> a[i];
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    int mx = -INF, mn = INF;
    for (int j = i; j <= n; ++j) {
      max_self(mx, a[j]);
      min_self(mn, a[j]);
      if (mx - mn > t)
        break;
      ++ans;
    }
  }
  cout << ans << '\n';
  return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3872)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3872/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3872/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)