0698 - nrpits

Enunt

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 nrpitsIN.txt 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 nrpitsOUT.txt va conține un singur număr reprezentând numărul de “gropi” ale șirului dat. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

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

Exemplul 1:

nrpitsIN.txt

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

nrpitsOUT.txt

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

Exemplul 2:

nrpitsIN.txt

1000001
12 1 10 3 4 11 5 8 7 9 2 6

nrpitsOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

def verifica_restricții(n, v):
    # Verificăm dacă N respectă restricțiile
    if not (2 <= n <= 1_000_000):
        return False
    # Verificăm dacă fiecare element din v respectă restricțiile
    for val in v:
        if not (1 <= val <= 1_000_000):
            return False
    return True

def main():
    with open("nrpitsIN.txt", "r") as fin:
        n = int(fin.readline())
        v = list(map(int, fin.readline().split()))

    # Verificăm restricțiile
    if not verifica_restricții(n, v):
        with open("nrpitsOUT.txt", "w") as fout:
            fout.write("Datele nu corespund restrictiilor impuse")
        return  # Oprim execuția dacă datele nu respectă restricțiile

    # Continuăm procesarea datelor deoarece acestea respectă restricțiile
    v = [0] + v
    st = [-1] * (n + 1)
    dr = [-1] * (n + 1)

    s = []
    for i in range(1, n + 1):
        while s and v[i] > v[s[-1]]:
            s.pop()
        if s:
            st[i] = s[-1]
        s.append(i)

    d = []
    for i in range(n, 0, -1):
        while d and v[i] > v[d[-1]]:
            d.pop()
        if d:
            dr[i] = d[-1]
        d.append(i)

    ans = sum(1 for i in range(1, n + 1) if st[i] != -1 and dr[i] != -1)

    with open("nrpitsOUT.txt", "w") as fout:
        fout.write(str(ans))

if __name__ == "__main__":
    main()