1221 (Editorial)

The problem can be shortened into , Given two arrays a_1,a_2,\ldots,a_n and b_1,b_2,\ldots,b_n , Determine the exact count of all different indices combinations where (a_i,a_j,b_k) with i<j or (a_k,b_i,b_j) with i<j forms a valid triangle.

A valid triangle is formed by its side lengths (a,b,c) when the three conditions hold simultaneously

WLOG, Say we've $a,b$ but we need to bound the range of $c$ :

Therefore |a-b|<c<a+b is the correct bound , and since all lengths are integers this is |a-b|<c\leq a+b-1. We can iterate the first two indices $i,j$ via ordinary brute force , the remaining question how to evaluate the count of triplets correctly without increasing the time complexity? , as we obtained the minimum $c$ we need is larger than |a-b| and largest must be less than a+b , This can be done with binary search ! , However , Firstly we need to ensure that both arrays are sorted , so first step before the actual procedure is to sort both arrays in O(n \log n) , Now we iterate as i<j we first assume we're working with triplet of first form (a_i,a_j,b_k) we need to look for count of valid b_k ,

The same process goes for triplet of the other type : (a_k,b_i,b_j) we need to look for count of valid a_k ,

. The mentioned "$\min$ index such that it exceeds a value $v$" is exactly same as 'bisect_right' in Python or 'upper_bound' in C++ , which is a binary search in O(\log n).

Therefore , The total time complexity is O(n^2 \log n).

from bisect import *

def solve():
    n=int(input())
    a=list(map(int,input().split()))
    b=list(map(int,input().split()))
    a.sort()
    b.sort()
    ans=0
    for i in range(n):
        for j in range(i+1,n):
            x,y=a[i],a[j]
            ans+=(bisect_right(b,x+y-1)-bisect_right(b,abs(x-y)))
            x,y=b[i],b[j]
            ans+=(bisect_right(a,x+y-1)-bisect_right(a,abs(x-y)))
    print(ans)
for _ in range(int(input())):
    solve()