Editing 3453 - jungla

== Cerinta ==
În junglă cresc foarte mulți copaci, de diferite înălțimi. Fiind pasionat de copacii din junglă, Gigel a notat pe o foaie înălțimile la care pot ajunge copacii din junglă. Fiind închis în casă, își pune, ca orice copil normal, tot felul de întrebări bizare. El s-a gandit să planteze pomii în linie, într-o anumită ordine, și astfel a obținut N numere, v[1], v[2], ..., v[N], unde V[i] reprezintă înălțimea copacului i. Apoi i-au venit în minte două întrebări.

Mai întâi vrea sa afle câți copaci plantați înaintea copacului cu numărul de ordine i au înălțimile mai mici ca acesta.A doua întrebare este mai speciala; Gigel se întreabă care ar fi dreptunghiul cu suprafața maximă liberă (adică neocupată de vreun copac) dacă ar încadra copacii într-o seră cu înălțimea egală cu înălțimea celui mai înalt copac plantat. Putem vizualiza sera ca pe un tablou bidimensional, cu colțul din stanga jos de coordonate (1,1) , iar cel din dreapta sus de coordonate (N,H), unde N este numărul de copaci, iar H este înâlțimea maximă a unui copac. În acest tablou copacul cu numărul de ordine i ocupă primele v[i] unități de pe coloana i, de jos in sus (v[i] reprezintă înălțimea copacului i).

== Date de intrare ==
Programul citește de la tastatură un număr p, care poate avea valorile 1 sau 2, în funcție de cerința problemei.

Pentru p = 1, următorul rând conține numerele N q. Următorul rând conține n valori, a i -a valoare reprezentând înălțimea copacului cu numarul de ordine. Rândul următor conține q numere; pentru fiecare număr i se cere numarul de copaci plantați înaintea copacului cu numărul de ordine i cu înălțimi mai mici ca acesta.

Pentru p = 2, următorul rând va conține doar numărul N, iar ultimul rând va conține N valori reprezentând înălțimile copacilor.

== Date de iesire ==
Pentru p = 1 programul va afișa q linii; pe fiecare linie se va afla raspunsul pentru fiecare dintre cele q numere date.

Pentru p = 2 programul fa afișa singur numar, reprezentând raspunsul pentru cerinta 2 , adică dreptunghiul liber de arie maximă.

== Restricti si precizari ==
*Pentru cerința 1, n ≤ 1000, iar pentru cerința 2, n ≤ 100.000
*înâlțimile copacilor vor fi numere naturale nenule mi mici decât 15.000
*1 ≤ q ≤ 2*n
*Pentru 25 de puncte cerința este 1.

== Exemplu 1 ==

;intrare
:1
:7 3
:4 2 6 8 3 4 2
:2 4 6

;iesire
;Datele introduse corespund restrictiilor impuse
:0
:3
:2


== Exemplul 2 ==

;intrare
:3
:12
:7 8 9 9 11 9 6 7 2 1 3

;iesire
;Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang='python'line>
def copaci_cu_inaltimi_mici(v):
    n = len(v)
    cnt_copaci_mici = [0] * n
    
    for i in range(1, n):
        for j in range(i):
            if v[i] > v[j]:
                cnt_copaci_mici[i] += 1

    return cnt_copaci_mici

# Exemplu de folosire
v = [3, 1, 4, 2, 5]
rezultat = copaci_cu_inaltimi_mici(v)
print(rezultat)

def suprafata_maxima_liber(v):
    n = len(v)
    stiva = []
    max_suprafata = 0

    for i in range(n):
        while stiva and v[i] <= v[stiva[-1]]:
            h = v[stiva.pop()]
            w = i if not stiva else i - stiva[-1] - 1
            max_suprafata = max(max_suprafata, h * w)
        stiva.append(i)

    while stiva:
        h = v[stiva.pop()]
        w = n if not stiva else n - stiva[-1] - 1
        max_suprafata = max(max_suprafata, h * w)

    return max_suprafata

# Exemplu de folosire
v = [3, 1, 4, 2, 5]
rezultat = suprafata_maxima_liber(v)
print(rezultat)
</sybtaxhighlight>