codeforces-scrape

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

1703F.md (1631B)


      1 Source: https://codeforces.com/problemset/problem/1703/F
      2 
      3 F. Yet Another Problem About Pairs Satisfying an Inequality
      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_1, a_2, \dots a_n$. Count the number of pairs of indices $1 \leq i, j \leq n$ such that $a_i \lt i \lt a_j \lt j$.
     22 
     23 Input
     24 
     25 The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.
     26 
     27 The first line of each test case contains an integer $n$ ($2 \leq n \leq 2 \cdot 10^5$) — the length of the array.
     28 
     29 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \leq a_i \leq 10^9$) — the elements of the array.
     30 
     31 It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$.
     32 
     33 Output
     34 
     35 For each test case, output a single integer — the number of pairs of indices satisfying the condition in the statement.
     36 
     37 Please note, that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 5
     45 
     46 8
     47 
     48 1 1 2 3 8 2 1 4
     49 
     50 2
     51 
     52 1 2
     53 
     54 10
     55 
     56 0 2 1 6 3 4 1 2 8 3
     57 
     58 2
     59 
     60 1 1000000000
     61 
     62 3
     63 
     64 0 1000000000 2
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 3
     71 0
     72 10
     73 0
     74 1
     75 ```
     76 
     77 Note
     78 
     79 For the first test cases the pairs are $(i, j)$ = $\{(2, 4), (2, 8), (3, 8)\}$.
     80 
     81 * The pair $(2, 4)$ is true because $a_2 = 1$, $a_4 = 3$ and $1 \lt 2 \lt 3 \lt 4$.
     82 * The pair $(2, 8)$ is true because $a_2 = 1$, $a_8 = 4$ and $1 \lt 2 \lt 4 \lt 8$.
     83 * The pair $(3, 8)$ is true because $a_3 = 2$, $a_8 = 4$ and $2 \lt 3 \lt 4 \lt 8$.