3705 - rectangles

Cerinta

Se consideră un șir de N 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 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 ieșire

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

Restricții și precizări

• 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

Ieșire

15

Explicație

Sunt 3 rectangle-sequences: (2; 3); (2; 3; 1); (3; 1). Ariile celor trei deptunghiuri ce le caracterizează sunt: 6, 6, 3.

Exemplul 2:

Intrare

100000000000
2 3 1

Ieșire

Datele nu corespund restrictiilor impuse

Rezolvare

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