2437 - Turnuri

Enunt

Cel mai nou proiect imobiliar din capitală este compus din N blocuri-turn, construite unul lângă altul, de-a lungul unui bulevard central și numerotate de la 1 la N. Pentru fiecare turn se cunoaște numărul etajelor din care este compus acesta și se mai știe că nu există două turnuri cu același număr de etaje. Ultimele norme urbanistice definesc coeficientul de frumusețe al turnului cu numărul T ca fiind numărul turnurilor din secvența de turnuri care începe cu turnul S, se termină cu turnul D și are următoarele proprietăți:

• 1 ≤ S ≤ T ≤ D ≤ N
• numărul etajelor fiecărui turn din secvență, cu excepţia turnului T, este mai mic decât numărul de etaje ale turnului T;
• Dacă S ≠ 1 atunci turnul S-1 este cel mai apropiat turn din stânga turnului T, care are un număr de etaje strict mai mare decât turnul T;
• Dacă D ≠ N atunci turnul D+1 este cel mai apropiat turn din dreapta turnului T, care are un număr de etaje strict mai mare decât turnul T;

Coeficientul de frumusețe al întregului ansamblu de turnuri este suma coeficienților de frumusețe avuţi de turnurile componente. Dezvoltatorul proiectului dorește să renunțe la unul dintre turnuri și să construiască în locul acestuia un restaurant subteran, acesta considerându-se un turn cu zero etaje. Dezvoltatorul dorește să calculeze coeficientul de frumusețe al ansamblului de turnuri, pentru fiecare posibilă amplasare a restaurantului.

Cerința

Cunoscând numărul N de turnuri și numărul etajelor fiecăruia, determinați coeficientul de frumusețe al ansamblului de turnuri pentru toate cele N posibilități de amplasare ale restaurantului, pe pozițiile 1, 2,…, N.

Date de intrare

Datele de intrare se citesc din fişierul turnuriIN.txt, care are următoarea structură:

- pe prima linie se află numărul natural N, reprezentând numărul de turnuri;

- pe a doua linie se află N valori naturale nenule, separate prin câte un spațiu, reprezentând numărul etajelor turnurilor;

Date de ieșire

Datele de ieşire se vor scrie în fişierul turnuriOUT.txt, pe linii separate, astfel: pe linia i (1 ≤ i ≤ N) se găsește un număr natural reprezentând coeficientul de frumusețe al ansamblului dacă restaurantul s-ar construi în locul turnului i. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări

• 1 ≤ N ≤ 100 000
• Numărul de etaje ale unui turn este un număr natural între 1 și 1 000 000 000
• Pentru teste în valoare de 30 de puncte, avem N ≤ 100
• Pentru teste în valoare de încă 30 de puncte, avem N ≤ 2000
• În concurs s-au acordat 10 puncte din oficiu. Aici se acordă pentru exemplul din enunț.

Exemplul 1:

turnuriIN.txt

7
10 3 1 7 8 6 5

turnuriOUT.txt

19
22
22
22
21
22
22

Explicație :

Figura 1 este reprezentarea grafică a fişierului de intrare.

Dacă restaurantul se construiește în locul turnului 1 (vezi figura 2), avem următorii coeficienți de frumusețe:

Restaurantul are coeficientul 1 (el însuși)

Turnul 2 are coeficientul 3 (secvența compusă din turnurile 1, 2 și 3)

Turnul 3 are coeficientul 1 (el însuși)

Turnul 4 are coeficientul 4 (secvența compusă din turnurile 1, 2, 3 și 4)

Turnul 5 are coeficientul 7 (secvența compusă din toate turnurile)

Turnul 6 are coeficientul 2 (secvența compusă din turnurile 6 și 7)

Turnul 7 are coeficientul 1 (el însuși)

Coeficientul de frumusețe al ansamblului este: 1 + 3 + 1 + 4 + 7 + 2 + 1 = 19

Exemplul 2:

turnuriIN.txt

100001
10 3 1 7 8 6 5

turnuriOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

def citeste_date():
    with open("turnuriIN.txt", "r") as fin:
        n = int(fin.readline().strip())
        v = [0] + [int(x) for x in fin.readline().split()]
    return n, v

def verifica_restrictii(N):
    if not (1 <= N <= 100000):
        return False, "Datele nu corespund restrictiilor impuse"
    return True, None

def calculeaza_stanga(n, v):
    st1, st2 = [0] * (n + 1), [0] * (n + 1)
    q = [[] for _ in range(n + 1)]
    st = []
    
    for i in range(1, n + 1):
        while st and v[i] >= v[st[-1]]:
            q[i].append(st.pop())
        st1[i] = st[-1] if st else 0
        st.append(i)

    for i in range(1, n + 1):
        t = st1[i]
        if 1 <= t <= n:
            while q[t] and v[i] >= v[q[t][0]]:
                q[t].pop(0)
        st2[i] = 0 if t == 0 or not q[t] else q[t][0]
    
    return st1, st2

def calculeaza_dreapta(n, v):
    dr1, dr2 = [0] * (n + 1), [0] * (n + 1)
    q = [[] for _ in range(n + 1)]
    dr = []
    
    for i in range(n, 0, -1):
        while dr and v[i] >= v[dr[-1]]:
            q[i].append(dr.pop())
        dr1[i] = dr[-1] if dr else n + 1
        dr.append(i)

    for i in range(n, 0, -1):
        t = dr1[i]
        if 1 <= t <= n:
            while q[t] and v[i] >= v[q[t][0]]:
                q[t].pop(0)
        dr2[i] = n + 1 if t == n + 1 or not q[t] else q[t][0]
    
    return dr1, dr2

def calc_fara_restaurant(n, dr1, st1):
    return sum(dr1[i] - st1[i] - 1 for i in range(1, n + 1))

def calc_cu_restaurant(n, suma, v, st1, st2, dr1, dr2):
    rez = [suma - (dr1[i] - st1[i] - 1) + 1 for i in range(n + 1)]
    for i in range(1, n + 1):
        if st1[i] != 0:
            rez[st1[i]] += st1[i] - st2[i]
        if dr1[i] != n + 1:
            rez[dr1[i]] += dr2[i] - dr1[i]
    return rez

def main():
    n, v = citeste_date()
    
    # Verificăm restricțiile
    valid, mesaj = verifica_restrictii(n)
    if not valid:
        with open("turnuriOUT.txt", "w") as fout:
            fout.write(mesaj)
        return
    
    st1, st2 = calculeaza_stanga(n, v)
    dr1, dr2 = calculeaza_dreapta(n, v)
    suma = calc_fara_restaurant(n, dr1, st1)
    rez = calc_cu_restaurant(n, suma, v, st1, st2, dr1, dr2)
    
    with open("turnuriOUT.txt", "w") as fout:
        for i in range(1, n + 1):
            fout.write(f"{rez[i]}\n")

if __name__ == "__main__":
    main()