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

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