Editing 3453 - jungla (section)

= 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>