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) ]

the code of algorithem :

// ██ ██ █████ █████ ██ ██ // ██ ██ ██ ██ ██ ██ ██ ██ // ████ ███████ ███████ ██ ██ // ██ ██ ██ ██ ██ ██ ██ // ██ ██ ██ ██ ██ ██████ ██

include <bits/stdc++.h>

using namespace std;

define int long long

const int maxn = 2e5 + 7, inf = 1e9 + 7; int n, ans, ab[maxn], ba[maxn];

bool cmp(int a, int b) { return a > b; } int DandD(int l, int r) { int ans = 0; if (r — l < 2) return 0; int mid = (r — l) / 2 + l; int a1 = DandD(l, mid); int a2 = DandD(mid, r); ans = a1 + a2; // cout << ans << endl; // cout << l << " " << r << endl; sort(ab + l, ab + mid, cmp); sort(ba + mid, ba + r, cmp); int p1 = l, p2 = mid; int s1 = mid — l, s2 = r — mid; while(p1 < mid && p2 < r) { // cout << p1 << " " << p2 << " cjsdicj " << ab[p1] << " " << ba[p2] << endl; if (ab[p1] > ba[p2]) { ans += r — p2; p1++; } else { p2++; } } //cout << ans << endl; return ans; }

void solve() { cout << DandD(0, n); }

void input() { cin >> n; int a[n], b[n]; for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < n; i++) cin >> b[i]; for (int i = 0; i < n; i++) { ab[i] = a[i] — b[i]; ba[i] = b[i] — a[i]; } } signed main() { input(), solve(); }