I know this is not the cleanest complexity for this problem, and there are better (O(n \log n)) solutions. I just wanted to share this Divide and Conquer approach because I found the idea interesting. I will also try to optimize and improve it later.

We define: [ d_i = a_i — b_i ]

Then the original condition:

[ a_i + a_j > b_i + b_j ]

can be rewritten as:

[ (a_i — b_i) + (a_j — b_j) > 0 ]

which means:

[ d_i > -(d_j) ]

Now define another array:

[ c_i = b_i — a_i = -d_i ]

So for every valid pair ((i,j)) with (i<j), we need:

[ d_i > c_j ]

We solve the problem using Divide and Conquer.

For a segment ([l,r)):

1. Recursively count all good pairs completely inside the left half.
2. Recursively count all good pairs completely inside the right half.
3. Count cross pairs where:

• (i) belongs to the left half,
• (j) belongs to the right half.

To count cross pairs efficiently:

• Sort the left part of array (d) in decreasing order.
• Sort the right part of array (c) in decreasing order.

Now use two pointers.

Suppose:

• pointer (p_1) iterates over the left half of (d),
• pointer (p_2) iterates over the right half of (c).

If:

[ d[p_1] > c[p_2] ]

then because the right half is sorted in decreasing order, all elements after (p_2) also satisfy the inequality.

Therefore we can add:

[ (r — p_2) ]

to the answer and move (p_1).

Otherwise we move (p_2).

This counts all cross pairs in linear time after sorting.

Complexity:

At every recursive level we process the current segment and count cross pairs using two pointers after sorting.

The overall complexity is:

[ O(n \log^2 n) ]

and the memory complexity is:

[ O(n) ]