Inversions Revisited
Practice
3 (4 votes)
Algorithms
Approved
Bit manipulation
Fenwick tree
Hard
Open
Trees
Problem
54% Success 3924 Attempts 50 Points 1s Time Limit 256MB Memory 1024 KB Max Code
Most of us know how to count the number of inversions in an array. An inversion in an array is a pair of indices(i,j) such that a[i]>a[j] and i < j.
In this problem you are given 2 arrays A and B and you have to return number of such pairs such that a[i]>b[j] and i < j.
Input Format:
First line contains n denoting the total number of elements.The next line contains n space separated integers of array A.This line is again followed by n space separated integers of array B.
Output Format:
Print the total number of pairs satisfying the above condition.
Constraints:
1<=n<=200000
1<=A[i]<=10^6
1<=B[i]<=10^6
Submissions
Please login to view your submissions
Similar Problems
Points:50
2 votes
Tags:
Data StructuresFenwick TreeFenwick treeHard
Points:50
22 votes
Tags:
ApprovedBit ManipulationData StructuresHardOpenReadySorting
Points:50
5 votes
Tags:
Segment treeAdvanced Data StructuresData StructuresFenwick (Binary Indexed) Trees
Editorial