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