1538C.md (1322B)
1 Source: https://codeforces.com/problemset/problem/1538/C 2 3 C. Number of Pairs 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given an array $a$ of $n$ integers. Find the number of pairs $(i, j)$ ($1 \le i \lt 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$). 22 23 For example, if $n = 3$, $a = [5, 1, 2]$, $l = 4$ and $r = 7$, then two pairs are suitable: 24 25 * $i=1$ and $j=2$ ($4 \le 5 + 1 \le 7$); 26 * $i=1$ and $j=3$ ($4 \le 5 + 2 \le 7$). 27 28 Input 29 30 The first line contains an integer $t$ ($1 \le t \le 10^4$). Then $t$ test cases follow. 31 32 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. 33 34 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$). 35 36 It is guaranteed that the sum of $n$ overall test cases does not exceed $2 \cdot 10^5$. 37 38 Output 39 40 For each test case, output a single integer — the number of index pairs $(i, j)$ ($i \lt j$), such that $l \le a_i + a_j \le r$. 41 42 Example 43 44 Input 45 46 ``` 47 4 48 3 4 7 49 5 1 2 50 5 5 8 51 5 1 2 4 3 52 4 100 1000 53 1 1 1 1 54 5 9 13 55 2 5 5 1 1 56 ``` 57 58 Output 59 60 ``` 61 2 62 7 63 0 64 1 65 ```