2051D.md (1626B)
1 Source: https://codeforces.com/problemset/problem/2051/D 2 3 D. Counting 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 a sequence $a$, consisting of $n$ integers, where the $i$-th element of the sequence is equal to $a_i$. You are also given two integers $x$ and $y$ ($x \le y$). 22 23 A pair of integers $(i, j)$ is considered interesting if the following conditions are met: 24 25 * $1 \le i \lt j \le n$; 26 * if you simultaneously remove the elements at positions $i$ and $j$ from the sequence $a$, the sum of the remaining elements is at least $x$ and at most $y$. 27 28 Your task is to determine the number of interesting pairs of integers for the given sequence $a$. 29 30 Input 31 32 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 33 34 Each test case consists of two lines: 35 36 * The first line contains three integers $n, x, y$ ($3 \le n \le 2 \cdot 10^5$, $1 \le x \le y \le 2 \cdot 10^{14}$); 37 * The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{9}$). 38 39 Additional constraint on the input: the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$. 40 41 Output 42 43 For each test case, output one integer — the number of interesting pairs of integers for the given sequence $a$. 44 45 Example 46 47 Input 48 49 ``` 50 7 51 52 4 8 10 53 54 4 6 3 6 55 56 6 22 27 57 58 4 9 6 3 4 5 59 60 3 8 10 61 62 3 2 1 63 64 3 1 1 65 66 2 3 4 67 68 3 3 6 69 70 3 2 1 71 72 4 4 12 73 74 3 3 2 1 75 76 6 8 8 77 78 1 1 2 2 2 3 79 ``` 80 81 Output 82 83 ``` 84 4 85 7 86 0 87 0 88 1 89 5 90 6 91 ``` 92 93 Note 94 95 In the first example, there are $4$ interesting pairs of integers: 96 97 1. $(1, 2)$; 98 2. $(1, 4)$; 99 3. $(2, 3)$; 100 4. $(3, 4)$.