Vizualizare sursă pentru „2654 - Sort All”

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