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

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()