# PBinfo #698 – nrpits – Rezolvare C++

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

## Enunț

Se dă un șir de N numere distincte a[1],a[2],..a[N]. Orice secvență a[i],a[i+1],...,a[j-1],a[j], 1 ≤ i + 1 < j ≤ n,  pentru care toate valorile a[k], i < k < j, sunt mai mici decât extremitățile a[i] și a[j],  o vom numi în continuare “groapă”.

Cerința
Scrieţi un program care va determina numărul “gropilor” din  șirul dat.

Date de intrare
Fișierul de intrare nrpits.in conţine pe prima linie numărul natural N. Pe linia a doua se află scrise cele N numere naturale ale șirului, separate prin spațiu.

Date de ieșire
Fișierul de ieșire nrpits.out va conține un singur număr reprezentând numărul de “gropi” ale șirului dat.

Restricții și precizări

2 ≤ N ≤ 1.000.000
1 ≤ a[i] ≤ 1.000.000, pentru fiecare 1 ≤ i ≤ N
orice “groapă” are cel puțin trei elemente

Exemplu:
nrpits.in

12
12 1 10 3 4 11 5 8 7 9 2 6
nrpits.out

8
Explicație
Cele opt “gropi” sunt:  
12 1 10
10 3 4
12 1 10 3 4 11
10 3 4 11
11 5 8
8 7 9
9 2 6
11 5 8 7 9

## Cod sursă C++

```cpp
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("nrpits.in");
ofstream fout("nrpits.out");
int m, n, k, p, cnt, c;
int a[1000001];
stack<int> stk;
int poz1[1000001]; // poz1[i] = k poz cel mai apropiat k din stanga, pt care a[k] > a[i]
int poz2[1000001]; // // poz1[i] = k poz cel mai apropiat k din dreapta, pt care a[k] > a[i]
int main()
{
    fin >> n;
    for ( int i = 1; i <= n; ++i )
    {
        fin >> a[i];
        while (!stk.empty() && a[i] > a[stk.top()])
            stk.pop();
        if ( !stk.empty() ) poz1[i] = stk.top();
        stk.push(i);
    }
    while ( !stk.empty() ) stk.pop();
    for ( int i = n; i > 0; --i )
    {
        while (!stk.empty() && a[i] > a[stk.top()])
            stk.pop();
        if ( !stk.empty() ) poz2[i] = stk.top();
        stk.push(i);
    }
    int cnt = 0, k, p;
    for ( int i = 3; i <= n; ++i )
        if ( a[i] > a[i-1] )
        {
            k = poz1[i]; if ( k == 0 ) k = 1;
            while ( k < i - 1)
            {
                p = poz2[k];  if ( p == 0 ) p = i + 1;
                if ( p < i ) k = p;
                else k++, cnt++;
            }
        }
    fout << cnt << '\n';
    fin.close();
    fout.close();
    return 0;
}
```

## Resurse

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