TRIPINV - Mega Inversions

no tags 

The n^2 upper bound for any sorting algorithm
is easy to obtain: just take two elements
that are misplaced with respect to each other
and swap them. Conrad conceived an algorithm
that proceeds by taking not two, but three misplaced
elements. That is, take three elements
ai > aj > ak with i < j < k and place them in
order ak; aj ; ai. Now if for the original algorithm
the steps are bounded by the maximum number
of inversions n(n-1)/2, Conrad is at his wits' end as
to the upper bound for such triples in a given sequence. He asks you to write a program
that counts the number of such triples.


The rst line of the input is the length of the sequence, 1 <= n <= 10^5.
The next line contains the integer sequence a1;
You can assume that all ai belongs [1; n].


Output the number of inverted triples.


3 3 2 1 Output: 2

hide comments
sri: 2011-10-15 20:00:06

why am i getting WA? is the result storable in long long int in c???

:-P: 2011-10-10 07:29:49


Last edit: 2011-10-12 20:41:18

Added by:Krzysztof Lewko
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Nordic programming contest