codeforces-scrape

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

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)$.