3705 - rectangles

From Bitnami MediaWiki

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

<syntaxhighlight lang="python3" line="1">

  1. 3705 - Rectangles

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

</syntaxhighlight>