# PBinfo #3239 – chain – Rezolvare C++

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

## Enunț

Se dă o secvență de N numere întregi a1, a2, …, aN. Pentru fiecare element ak (k = 1, 2, ...,n) vom determina primul element mai mare decât ak, dacă există. Îl notăm cu ak1. Apoi, pentru ak1 facem același lucru și elementul găsit îl notăm cu ak2, și așa mai departe până ieșim în afara șirului. Se formează secvența ak1, ak2, …, pe care o numim chain începând cu poziția k.

Cerința
Scrieți un program care, pentru orice poziție k afișează lungimea secvenței chain corespunzătoare.

Date de intrare
Pe prima linie a intrării standard se dă valoarea N. Pe a doua linie se dau elementele șirului, separate prin spații.

Date de ieșire
Pe o linie a ieșirii standard, programul va scrie șirul valorilor ce reprezintă lungimile secvențelor chain corespunzătoare elementelor șirului de intrare. Fiecare două numere consecutive trebuie separate printr-un singur spațiu.

Restricții și precizări

0 < N < 500.000
0 < ai < 1.000.000, pentru fiecare i = 1..N.

Exemplu:
Intrare

11
3 2 4 2 11 2 7 5 8 10 6
Ieșire

2 2 1 1 0 3 2 2 1 0 0

## Cod sursă C++

```cpp
#include<iostream>
#include<iomanip>
#include<stack>
using namespace std;
const int N=1000002;
int n;
int a[N];
int p[N];
int d[N];
int main()
{
  cin >> n;
  for(int i=0;i<n;i++) cin >> a[i];
// O(n)
  stack<int> s;
  for(int i=1;i<n;i++)
  {
    s.push(i-1);
    while(!s.empty())
    {
      int j=s.top();
      if(a[j]>=a[i]) break;
      if(a[j]<a[i]) {p[j]=i; s.pop();}
    }
  }
// chains
   d[n-1]=0;
   for(int i=n-2;i>=0;i--)
   {
     if(p[i]==0) d[i]=0;
     else d[i]=1+d[p[i]];
   }
    cout << d[0];
    for(int i=1; i<n; i++) cout << " " << d[i];
    cout << endl;
}
```

## Resurse

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