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ă.

Restricti1 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 mai 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="python3"line="1"> 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

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

</syntaxhighlight>