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
|
aditya930:
2016-12-27 23:53:59
use enhanced merge sort and long long to get AC !! |
|
supercool2204:
2016-12-27 20:40:05
Last edit: 2017-06-02 15:15:34 |
|
aditya9125:
2016-12-25 21:12:12
Use long long for no_of_inversions as max no of inversions could occur in the case when list has all the elements in strictly decreasing order ,i.e max_inversions=n(n-1)/2; |
|
vstepano:
2016-12-15 19:36:07
I managed to solve this problem with 2 different programs. One using Merge Sort and one using the BIT (Binary Indexed Tree Peter M. Fenwick). My implementation that used Merge sort had a lot more code than the BIT one, but in the end the Merge sort solution was faster. |
|
sergio471:
2016-12-08 21:39:57
too many WA because size_t is not necessarily unsigned long long |
|
mohitgupta07:
2016-12-02 12:13:39
Got my error..did my code in eclipse..and just copy pasted it..forgot to remove my package line in the code...costed my NZEC :P :P :P |
|
|
mohitgupta07:
2016-12-02 12:03:39
Simple .. BitMasking.. I mean Fenwick rocks :) :) Simple concept and simple logic.. Also can anyone explain why java gave NZEC for the same code in c++. Also take great care of choosing your data type. costed me 3 WA's . Nice ques and a good way to understand Fenwick :) . |
|
rohan_12_11:
2016-11-16 10:34:27
use long long to get AC. Use ORDER STATISTIC BST algorithm.
|
|
code_inception:
2016-11-10 18:57:11
good one to do with BIT .... will give more understanding of BIT |
|
s_jindal00:
2016-11-10 16:49:21
For INPUT {5,2,3,8,6,1} : OUTPUT must be 8 but answer is 5 in sample input! Is it Wrong?????? |
| 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