Editing 3239 - chain

== Enunt ==

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

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

= Date de intrare =
Pe prima linie a intrării standard se dă valoarea <code>N</code>. 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. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>0 < N < 500.000</code>
* <code>0 < ai</code> <code>< 1.000.000</code>, pentru fiecare <code>i = 1..N</code>.

= Exemplul 1: =
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

= Exemplul 2: =
Intrare
 0
 123
Ieșire
 Datele nu corespund restrictiilor impuse

== Rezolvare == 

<syntaxhighlight lang="python3" line="1">
def verifica_restrictii(n, a):
    if not (0 < n < 500000):
        return "Datele nu corespund restrictiilor impuse"
    for i in range(n):
        if not (0 < a[i] < 1000000):
            return "Datele nu corespund restrictiilor impuse"
    return "Datele corespund restrictiilor impuse"

def main():
    n = int(input())
    a = list(map(int, input().split()))

    mesaj = verifica_restrictii(n, a)
    if mesaj != "Datele corespund restrictiilor impuse":
        print(mesaj)
        return

    p = [0]*n
    d = [0]*n

    # O(n)
    s = []
    for i in range(1, n):
        s.append(i-1)
        while s:
            j = s[-1]
            if a[j] >= a[i]:
                break
            if a[j] < a[i]:
                p[j] = i
                s.pop()

    # chains
    d[n-1] = 0
    for i in range(n-2, -1, -1):
        if p[i] == 0:
            d[i] = 0
        else:
            d[i] = 1 + d[p[i]]

    print(' '.join(map(str, d)))

if __name__ == "__main__":
    main()

</syntaxhighlight>