Inversions Revisited
Practice
3 (4 votes)
Algorithms
Approved
Bit manipulation
Fenwick tree
Hard
Open
Trees
Problem
54% Success 3927 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
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:50
1 votes
Tags:
Advanced Data StructuresData StructuresDepth First SearchFenwick TreeFenwick treeHardOpentreap
Points:50
16 votes
Tags:
HardLoopsTrees
Points:50
22 votes
Tags:
ApprovedBit ManipulationData StructuresHardOpenReadySorting
Editorial
Login to unlock the editorial