Editing 3705 - rectangles

== Cerinta ==

Se consideră un șir de <code>N</code> numere naturale. Numim rectangle-sequence orice secvență continuă din șir (formată din elemente situate pe poziții consecutive) care conține cel puțin două elemente. Fiecare rectangle-sequence este caracterizată de un dreptunghi cu lungimile laturilor egale cu cele mai mari două elemente din cadrul ei.

= Cerința =
Să se calculeze restul împărțirii sumei ariilor dreptunghiurilor ce caracterizează toate rectangle-sequences din șir la numărul <code>1.000.000.007</code>.

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

= Date de ieșire =
Ieșirea conține numărul de determinat, modulo <code>1.000.000.007</code>. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

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

= Exemplul 1: =
Intrare
 3
 2 3 1
Ieșire
 15

=== Explicație ===
Sunt <code>3</code> rectangle-sequences: <code>(2; 3)</code>; <code>(2; 3; 1)</code>; <code>(3; 1)</code>. Ariile celor trei deptunghiuri ce le caracterizează sunt: <code>6</code>, <code>6</code>, <code>3</code>.

== Exemplul 2: ==
Intrare
 100000000000
 2 3 1
Ieșire
 Datele nu corespund restrictiilor impuse

== Rezolvare == 
<syntaxhighlight lang="python3" line="1">
MaxN = 1000010
mod = 10**9 + 7

v = [0] * MaxN
left1 = [0] * MaxN
left2 = [0] * MaxN
right1 = [0] * MaxN
right2 = [0] * MaxN

def multiply(a, b, c, d):
    return ((a * b) % mod) * ((c * d) % mod) % mod

def citeste_si_verifica_elemente(n):
    print(f"Introduceți {n} elemente (fiecare urmat de Enter):")
    v_temp = []
    for i in range(1, n + 1):
        try:
            x = int(input(f"Elementul {i}: "))
            if not (1 <= x <= 10**9):
                print("Datele nu corespund restricțiilor impuse")
                return None
            v_temp.append(x)
        except ValueError:
            print("Datele nu corespund restricțiilor impuse")
            return None
    return v_temp

def main():
    try:
        n = int(input("Introduceți lungimea șirului: "))
        if not (1 <= n <= 10**6):
            print("Datele nu corespund restricțiilor impuse")
            return
    except ValueError:
        print("Datele nu corespund restricțiilor impuse")
        return
    
    v_input = citeste_si_verifica_elemente(n)
    if v_input is None:
        return
    
    v[1:n+1] = v_input

    for i in range(1, n+1):
        left1[i] = left2[i] = 0
        right1[i] = right2[i] = n + 1
    
    st1, st2, aux = [], [], []
    for i in range(1, n+1):
        while st2 and v[i] > v[st2[-1]]:
            right2[st2[-1]] = i
            st2.pop()
        while st1 and v[i] > v[st1[-1]]:
            right1[st1[-1]] = i
            aux.append(st1.pop())
        st1.append(i)
        while aux:
            st2.append(aux.pop())
    
    st1.clear()
    st2.clear()
    
    for i in range(n, 0, -1):
        while st2 and v[i] >= v[st2[-1]]:
            left2[st2[-1]] = i
            st2.pop()
        while st1 and v[i] >= v[st1[-1]]:
            left1[st1[-1]] = i
            aux.append(st1.pop())
        st1.append(i)
        while aux:
            st2.append(aux.pop())
    
    sol = 0
    for i in range(1, n+1):
        if left1[i] > 0:
            a = left1[i] - left2[i]
            b = right1[i] - i
            sol += multiply(a, b, v[i], v[left1[i]])
        if right1[i] < n + 1:
            a = i - left1[i]
            b = right2[i] - right1[i]
            sol += multiply(a, b, v[i], v[right1[i]])
    
    sol %= mod
    print(sol)

if __name__ == "__main__":
    main()

</syntaxhighlight>