Editing 3705 - rectangles

== Cerinta ==

Să se calculeze restul împărțirii sumei ariilor dreptunghiurilor ce caracterizează toate rectangle-sequences din șir la numărul 1.000.000.007.

== Date de intrare ==

Prima linie contine numărul natural nenul N, reprezentând numărul elementelor din șir, iar linia a doua conține, separate prin câte un spațiu, cele N elemente. Întrucât volumul datelor de intrare este foarte mare, vă recomandăm, în cazul în care folosiți pentru citire biblioteca iostream din standardul C++, să adaugați la începutul funcției main urmatoarele instrucțiuni:

*std :: iosbase :: sync_with_stdio (false);
*std :: cin.tie(0);

== Date de iesire ==

Ieșirea conține numărul de determinat, modulo 1.000.000.007.

== Restrictii si precizari

*1 ≤ n ≤ 1.000.000
*1 ≤ orice element din șir 1 ≤ 1.000.000.000
*Subtask 1 (13 puncte): N ≤ 2000
*Subtask 2 (23 puncte): N ≤ 100.000 și există cel mult 100 de numere distincte în șir.
*Subtask 3 (27 puncte): N ≤ 200.000
*Subtask 4 (37 puncte): nu există restricții suplimentare

== Exemplul 1 ==

; intrare

:3
:2 3 1

; iesire

:Datele introduse corespund restrictiilor impuse.

:15

==Exemplul 2 ==

; intrare 

:4
:3 1 2

; iesire

:Datele nu corespund restrictiilor impuse.

== Rezolvare == 
<syntaxhighlightlang="python3"line="1"

def rest_suma_arii_rectangle_sequences(arr):
    mod = 1000000007
    n = len(arr)

    stack = []
    suma_arii = 0

    for i in range(n):
        while stack and arr[i] >= arr[stack[-1]]:
            h = arr[stack.pop()]
            w = i if not stack else i - stack[-1] - 1
            suma_arii = (suma_arii + h * w) % mod
        stack.append(i)

    while stack:
        h = arr[stack.pop()]
        w = n if not stack else n - stack[-1] - 1
        suma_arii = (suma_arii + h * w) % mod

    return suma_arii

# Exemplu de folosire
sir = [2, 5, 1, 4, 6, 3]
rezultat = rest_suma_arii_rectangle_sequences(sir)
print("Restul împărțirii sumei ariilor la 1.000.000.007 este:", rezultat)

<syntaxhighlight>