Editing 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 <code>N</code> numere, <code>v[1], v[2], ..., v[N]</code>, unde <code>V[i]</code> reprezintă înălțimea copacului <code>i</code>. 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 <code>i</code> 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 <code>(1,1)</code> , iar cel din dreapta sus de coordonate <code>(N,H)</code>, unde <code>N</code> este numărul de copaci, iar <code>H</code> este înâlțimea maximă a unui copac. În acest tablou copacul cu numărul de ordine <code>i</code> ocupă primele <code>v[i]</code> unități de pe coloana <code>i</code>, de jos in sus (<code>v[i]</code> reprezintă înălțimea copacului <code>i</code>).

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

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

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

= Date de ieșire =
Pentru <code>p = 1</code> programul va afișa <code>q</code> linii; pe fiecare linie se va afla raspunsul pentru fiecare dintre cele <code>q</code> numere date.

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

= Restricții și precizări =

* Pentru cerința 1, <code>n ≤ 1000</code>, iar pentru cerința 2, <code>n ≤ 100.000</code>
* înâlțimile copacilor vor fi numere naturale nenule mi mici decât <code>15.000</code>
* <code>1 ≤ q ≤ 2*n</code>
* 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: <code>p=1</code> deci se rezolvă doar cerința 1. Inainte de copacul cu numărul de ordine <code>2</code> nu există copaci cu înalțimi mai mici, înainte de copacul cu numărul de ordine <code>4</code> există <code>3</code> copaci mai mici, iar înainte de copacul <code>6</code> există <code>2</code> 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 <code>o</code> reprezinta zona liberă, iar <code>1</code> reprezintă o zona ocupată de copac. Suprafața dreptunghiulară maximă este de <code>20</code> 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>