The problem can be expressed in mathematical expressions as: “how many pairs \((i, j)\) are there such that \(A_i\geq A_j\) and \(B_i\leq B_j\)?” (\(i\) denotes the gift for Takahashi and \(j\) for Aoki).

By applying coordinate compressions, we may assume that \(1\leq A_i,B_i\leq N\). For simplicity, we first assume that no \((i,j)\) satisfies \((A_i,B_i)=(A_j,B_j)\).

If we inspect each \(i\) in the increasing order of \(A_i\), ties broken by the decreasing order of \(B_i\), the number of applicable \(j\)’s paired to the \(i\) is the number of such gifts inspected so far (including itself) that \(B_i\leq B_j\). The number can be found fast with segment trees.

Even if there exists \((i,j)\) such that \((A_i,B_i)=(A_j,B_j)\), it can be solved similarly by appropriately grouping them.

Therefore, the problem has been solved in a total of \(O(N\log N)\) time.

Sample code (C++)