INVCNT - Inversion Count
Let A[0...n - 1] be an array of n distinct positive integers. If i < j and A[i] > A[j] then the pair (i, j) is called an inversion of A. Given n and an array A your task is to find the number of inversions of A.
Input
The first line contains t, the number of testcases followed by a blank space. Each of the t tests start with a number n (n <= 200000). Then n + 1 lines follow. In the ith line a number A[i - 1] is given (A[i - 1] <= 10^7). The (n + 1)th line is a blank space.
Output
For every test output one line giving the number of inversions of A.
Example
Input: 2 3 3 1 2 5 2 3 8 6 1 Output: 2 5
hide comments
|
Erti-Chris Eelmaa:
2013-06-25 16:49:53
0.49 :-)) |
|
Vipul Pandey:
2013-06-19 19:48:22
got AC in the first attempt! just use merge sort with a bit modification. But a good one to learn a new thing. |
|
virtuazx:
2013-06-12 09:38:08
Be careful about the typecasting and longlong stuff....It kills a lot of your time!! |
|
ওয়াসী (Wasi):
2013-04-20 18:51:16
AC at first try...
|
|
Tony Stark:
2013-04-15 16:21:46
I have to agree with mister Kent. Last edit: 2013-04-03 13:03:25 |
|
luccasiau:
2013-04-15 16:21:46
Binary Indexed Trees are much more cooler than merge sort :) |
|
ankitsablok89:
2013-04-15 16:21:46
Easy one with Merge Sort :) |
|
suyog patil:
2013-04-15 16:21:46
easy 1 with merge sort!!! try ur college assignment program..:P |
|
Akash Goel:
2013-04-15 16:21:46
changing the no of inversions to long long didnt help, still stuck at TLE. :( |
|
Aman Verma:
2013-04-15 16:21:46
Guya just long long dis cost me much .. not only change the inversion_count to long long but change the array holding it also to long long
|
| Added by: | Paranoid Android |
| Date: | 2010-03-06 |
| Time limit: | 3.599s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: PERL6 |
RSS