codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```