3453 - jungla

Cerința

Î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 ieșire

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

Restricții și precizări

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

Exemplul 1:

Intrare

1
7 3
4 2 6 8 3 4 2
2 4 6

Ieșire

0
3
2

Exemplul 2:

Intrare

2
11
4 6 5 4 6 8 8 10 6 3 2

Ieșire

20

Explicație

Pentru exemplul 1: p=1 deci se rezolvă doar cerința 1. Inainte de copacul cu numărul de ordine 2 nu există copaci cu înalțimi mai mici, înainte de copacul cu numărul de ordine 4 există 3 copaci mai mici, iar înainte de copacul 6 există 2 copaci mai mici.

Pentru exemplul 2, sera ar arăta astfel:

o o o o o o o 1 o o
o o o o o o o 1 o o
o o o o o 1 1 1 o o
o o o o o 1 1 1 o o
o 1 o o 1 1 1 1 o o
o 1 1 o 1 1 1 1 o o
1 1 1 1 1 1 1 1 o o
1 1 1 1 1 1 1 1 1 o
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1

Unde o reprezinta zona liberă, iar 1 reprezintă o zona ocupată de copac. Suprafața dreptunghiulară maximă este de 20 de unități.

Exemplul 3:

Intrare

2
123123213

Ieșire

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def verifica_restricții(cer, n, q=None, v=None):

   if v and any(h <= 0 or h >= 15000 for h in v):
       print("Datele nu corespund restrictiilor impuse")
       return False
   
   if cer == 1:
       if not (1 <= n <= 1000) or not (1 <= q <= 2*n):
           print("Datele nu corespund restrictiilor impuse")
           return False
   elif cer == 2:
       if not (1 <= n <= 100000):
           print("Datele nu corespund restrictiilor impuse")
           return False
   else:
       print("Cerința specificată este invalidă.")
       return False
   return True

def main():

   cer = int(input())
   if cer == 1:
       n, q = map(int, input().split())
       if not verifica_restricții(cer, n, q):
           return
       v = [0] + list(map(int, input().split()))
       queries = list(map(int, input().split()))
       for j in queries:
           copaci = 0
           for i in range(1, j):
               if v[i] < v[j]:
                   copaci += 1
           print(copaci)
   elif cer == 2:
       n = int(input())
       if not verifica_restricții(cer, n):
           return
       v = [0] + list(map(int, input().split()))
       max_height = max(v)
       for i in range(1, n + 1):
           v[i] = max_height - v[i]
       st = [0] * (n + 1)
       dr = [0] * (n + 1)
       stack = []
       for i in range(1, n + 1):
           while stack and v[stack[-1]] >= v[i]:
               stack.pop()
           st[i] = stack[-1] if stack else 0
           stack.append(i)
       stack = []
       for i in range(n, 0, -1):
           while stack and v[stack[-1]] >= v[i]:
               stack.pop()
           dr[i] = stack[-1] if stack else n + 1
           stack.append(i)
       arie_max = 0
       for i in range(1, n + 1):
           arie_max = max(arie_max, v[i] * (dr[i] - st[i] - 1))
       print(arie_max)

if __name__ == "__main__":

   main()

</syntaxhighlight>