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
|
munjal:
2016-09-23 20:18:01
long long long !!!!!!!!!!!!!!!!!!!
|
|
Romil Jain:
2016-08-16 05:59:44
Got several WA because of int.
|
|
kunal todi:
2016-08-05 11:06:06
used mergesort in c++..but getting TLE..
|
|
iharsh234:
2016-07-22 11:53:18
I ll do this some day!!
|
|
|
iharsh234:
2016-07-22 11:53:18
Last edit: 2016-07-22 11:53:42 |
|
Bruce:
2016-07-20 11:10:11
Using mergesort and Python. Generated a test case with n = 16000 and response was instant. But when submitting I'm getting time limit exceeded. Are further optimisations required? |
|
liuxueyang:
2016-07-17 15:16:16
@praval_singhal Thanks for your remind. I shouldn't use int for the ans. :-(
|
|
davidgalehouse:
2016-07-17 07:41:55
I don't know what BIT is and it seems too complicated. I did this with an ad hoc binary search tree. Add array values to BST with some bookkeeping. |
|
shubiks:
2016-07-14 08:20:08
Great problem for learning application of Fenwick tree! :)
|
|
praval_singhal:
2016-07-12 19:18:18
Got WA because of INT. |
| 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