Chặt nhị phân hay

Adi is the coach of his football team.
He wants to form a team in which there are two defenders and one striker
For this he will select two defenders from list A and one striker from B such that the strength of j th player is greater than ith player and strength of attacker is grater than both the defenders.
In other words A[ i ] < A[ j ] < B[ k ] and index i<j.
He is intersted in finding the number of teams

---

INPUT
First line contains an integer N denoting the size of list A and B.
Next line contain N space separated integers dentoing the array A.
Next line contain N space separated integers dentoing the array B .

---

OUTPUT
Find the number of teams possible such that A[ i ] <A[ j ] < B[ k] and i<j..

---

CONSTRAINT
$1\le N\le 5000$
$1\le A[i]\le {10}^9$
$1\le B[i]\le {10}^9$

SAMPLE INPUT

 

5
1 3 2 3 4
2 1 3 3 4  

SAMPLE OUTPUT

 

6

Explanation

The possible teams are
(1,3,4), (1,2,3) , (1,2,3) ,(1,2,4), (1,3,4) , (2,3,4)
Note that these are values given not the index.

Lời giải:

#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,i,j,low,high,mid;
  cin>>n;
  long unsigned int a[n],b[n],val=0,k;
  for(i=0;i<n;i++) cin>>a[i];
  for(i=0;i<n;i++) cin>>b[i];
  sort(b,b+n);
  for(i=0;i<n;i++){
    for(j=i+1;j<n;j++){
        if(a[i]<a[j]){
            if(b[0]>a[j]) val+=n;
            else if(b[n-1]<=a[j]) val+=0;
            else{
                low=0;high=n-1;
                while(1){
                    mid=low+(high-low)/2;
                    if(low==mid) break;
                    if(b[mid]<(a[j]+1)) low=mid+1;
                    else high=mid;
                }
                if(b[low]<=a[j]) low++;
                else if(low>0&&b[low-1]>a[j]) low--;
                val+=n-low;
            }
        }
    }
  }
  cout<<val;
  return 0;
}