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
osman_goni_:
2022-08-08 17:59:27
Can this problem can be solved using Segment tree ? |
|
spongecodes:
2022-01-11 20:03:21
why is my solution accepted in CPP 14 but giving WA in C++ ? |
|
new_mutant:
2022-01-03 15:17:13
you have given that arr[i-1]<=10^7 , but it causes int overflow, when i used long long it got submitted, please correct it. Last edit: 2022-01-03 15:17:27 |
|
atishya_20:
2021-12-27 07:23:11
AC in one GO Using ordered set |
|
mohit_010:
2021-11-13 08:37:16
<snip>
|
|
4444:
2021-11-03 13:52:57
@sabkx thanks a lot for the long long int comment |
|
sabkx:
2021-10-03 07:06:22
EZ AC in second go! use long long instead of int. Merge sort works with 0.11 second |
|
jdmoyle:
2021-08-19 06:33:52
Fenwick Tree :D, return type long long int |
|
ss_sri:
2021-08-16 11:15:07
IDK but i am not able to solve it using merge sort, it says SEGMENTATION FAULT.
|
|
amish3:
2021-06-30 06:33:50
Getting TLE, even after using merge sort algorithm and scanf/printf. Any idea. Why it is so |
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 |