RebecaBud: Pagină nouă: == Enunt == Pentru un șir de numere A se definește următoarea funcție de cost: f(A)=1⋅v1+2⋅v2+…+k⋅vk , unde [v1,v2,…,vk] sunt valorile distincte ale lui A , ordonate crescător. == Cerinţa == Fiind dat un șir de N numere naturale A, să se calculeze suma aplicării funcției f pe toate subsecvențele lui A (i.e. suma după (1 ≤ i ≤ j ≤ N) din f(A[i...j]), unde A[i…j] este subsecvența de la i la j). == Date de intrare == Fișierul sortall.in conțin...

2024-06-03T17:16:37Z

Pagină nouă: == Enunt == Pentru un șir de numere A se definește următoarea funcție de cost: f(A)=1⋅v1+2⋅v2+…+k⋅vk , unde [v1,v2,…,vk] sunt valorile distincte ale lui A , ordonate crescător. == Cerinţa == Fiind dat un șir de N numere naturale A, să se calculeze suma aplicării funcției f pe toate subsecvențele lui A (i.e. suma după (1 ≤ i ≤ j ≤ N) din f(A[i...j]), unde A[i…j] este subsecvența de la i la j). == Date de intrare == Fișierul sortall.in conțin...

New page

== Enunt ==
Pentru un șir de numere A
se definește următoarea funcție de cost: f(A)=1⋅v1+2⋅v2+…+k⋅vk
, unde [v1,v2,…,vk]
sunt valorile distincte ale lui A
, ordonate crescător.
== Cerinţa ==
Fiind dat un șir de N numere naturale A, să se calculeze suma aplicării funcției f pe toate subsecvențele lui A (i.e. suma după (1 ≤ i ≤ j ≤ N) din f(A[i...j]), unde A[i…j] este subsecvența de la i la j).
== Date de intrare ==
Fișierul sortall.in conține pe prima linie numărul natural N. Linia a doua conține N numere naturale separate prin spațiu, reprezentând elementele șirului A.
== Date de ieșire ==
Fișierul sortall.out va conține răspunsul modulo 1 000 000 007.
== Restricţii şi precizări ==
* 1 ≤ N ≤ 50 000
* 1 ≤ Vi ≤ N
* Pentru 10 puncte 1 ≤ N ≤ 100
* Pentru alte 15 puncte 1 ≤ N ≤ 1000
* Pentru alte 15 puncte 1 ≤ N ≤ 5000
* Pentru alte 20 de puncte se garanteză că valorile din șir sunt distincte
== Exemplul 1 ==
; sortall.in

3
1 3 2
; sortall.out

35

<br>

== Exemplul 2 ==
; sortall.in

8
4 3 4 4 7 1 2 1
; sortall.out

864
<br>

== Rezolvare ==
<syntaxhighlight lang="python" line>
MOD = 1000000007

def solve(N, A):
freq = {}
total_sum = 0

for i in range(N):
curr_sum = 0

for num in freq:
if num <= A[i]:
curr_sum += (i - freq[num] + 1) * num * (freq[num] - freq.get(num - 1, 0))
curr_sum %= MOD

total_sum += curr_sum
total_sum %= MOD

freq[A[i]] = i + 1

return total_sum

def main():
with open("sortall.in", "r") as fin:
N = int(fin.readline())
A = list(map(int, fin.readline().split()))

result = solve(N, A)

with open("sortall.out", "w") as fout:
fout.write(str(result) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

2654 - Sort All - Revision history