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

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