|
|
back to threadReply to message- Messages should be written in English and correspond to the matter of the website.
- Messages should not contain offences and obscene words.
- Messages should not contain correct solutions.
It took pretty long time 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.
|
|
|