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

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

Loading...
Results
Custom Input
Run your code to see the output
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