Timus Online Judge
About Online Judge
Frequently asked questions
Update your info
back to board
Discussion of Problem
It took pretty long time
17 Jul 2017 16:52
It was hard to understand how to calculate the answer.
It is relatively easy to invent a correct solution when you know the expected time complexity.
Solve the task online, read elements one by one.
So, you have dp[i][j] = count of different j-inversions ending at element number j.
dp[i] [j] =sum (dp[p] [j-1]) for all p>i.
The answer is sum(dp[i] [k]) for all i=0...n-1.
As mentioned below, an array of Fenwick trees is your friend.
Timus Online Judge Team
. All rights reserved.