Number of Pairs (Codeforces 1538C)
Tags: Math, two pointers

You are given an array $$$a$$$ of $$$n$$$ integers. Find the number of pairs $$$(i, j)$$$ ($$$1 \le i < j \le n$$$) where the sum of $$$a_i + a_j$$$ is greater than or equal to $$$l$$$ and less than or equal to $$$r$$$ (that is, $$$l \le a_i + a_j \le r$$$).For example, if $$$n = 3$$$, $$$a = [5, 1, 2]$$$, $$$l = 4$$$ and $$$r = 7$$$, then two pairs are suitable:   $$$i=1$$$ and $$$j=2$$$ ($$$4 \le 5 + 1 \le 7$$$);  $$$i=1$$$ and $$$j=3$$$ ($$$4 \le 5 + 2 \le 7$$$). 

Input: The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$). Then $$$t$$$ test cases follow.The first line of each test case contains three integers $$$n, l, r$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le l \le r \le 10^9$$$) — the length of the array and the limits on the sum in the pair.The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).It is guaranteed that the sum of $$$n$$$ overall test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output a single integer — the number of index pairs $$$(i, j)$$$ ($$$i < j$$$), such that $$$l \le a_i + a_j \le r$$$.


Sample Inputs:
4
3 4 7
5 1 2
5 5 8
5 1 2 4 3
4 100 1000
1 1 1 1
5 9 13
2 5 5 1 1

Sample Outputs:
2
7
0
1

Solution (Python):
def spot_edges(ai, l, r):
    return (l - ai, r - ai)

def solve(n, a, l, r):
    a.sort()
    count = 0
    i = 0
    j = n - 1
    while i < j:
        if a[i] + a[j] <= r:
            count += j - i
            i += 1
        else:
            j -= 1
    i = 0
    j = n - 1
    while i < j:
        if a[i] + a[j] < l:
            count -= j - i
            i += 1
        else:
            j -= 1
    return count

def main():
    t = int(input())
    for i in range(t):
        (n, l, r) = [int(x) for x in input().split()]
        a = [int(x) for x in input().split()]
        print(solve(n, a, l, r))
main()

Solution (Python):
def contarSumas(arr, lim):
    izq = 0
    der = len(arr) - 1
    res = 0
    while izq < der:
        if arr[izq] + arr[der] > lim:
            der -= 1
        else:
            res += der - izq
            izq += 1
    return res
casos = int(input())
for _ in range(casos):
    firsData = [int(x) for x in input().split(' ')]
    arr = [int(x) for x in input().split(' ')]
    arr.sort()
    print(contarSumas(arr, firsData[2]) - contarSumas(arr, firsData[1] - 0.1))

Solution (Python):
import bisect

def solve(arr, l, r):
    arr.sort()
    (lo, hi) = (0, len(arr) - 1)
    res = 0
    while lo < hi:
        tot = arr[lo] + arr[hi]
        if l <= tot <= r:
            ix = bisect.bisect_left(arr, l - arr[lo])
            res += hi - max(lo, ix - 1)
            lo += 1
        elif tot < l:
            lo += 1
        elif tot > r:
            hi -= 1
    return res
if __name__ == '__main__':
    t = int(input())
    res = []
    for i in range(t):
        (n, l, r) = list(map(int, input().split(' ')))
        arr = list(map(int, input().split(' ')))
        res.append(solve(arr, l, r))
    for i in range(t):
        print(res[i])