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

Exemplul 2

sortall.in

 8
 4 3 4 4 7 1 2 1

sortall.out

 864

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>