1284B.md (2408B)
1 Source: https://codeforces.com/problemset/problem/1284/B 2 3 B. New Year and Ascent Sequence 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 1024 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 A sequence $a = [a_1, a_2, \ldots, a_l]$ of length $l$ has an ascent if there exists a pair of indices $(i, j)$ such that $1 \le i \lt j \le l$ and $a_i \lt a_j$. For example, the sequence $[0, 2, 0, 2, 0]$ has an ascent because of the pair $(1, 4)$, but the sequence $[4, 3, 3, 3, 1]$ doesn't have an ascent. 22 23 Let's call a concatenation of sequences $p$ and $q$ the sequence that is obtained by writing down sequences $p$ and $q$ one right after another without changing the order. For example, the concatenation of the $[0, 2, 0, 2, 0]$ and $[4, 3, 3, 3, 1]$ is the sequence $[0, 2, 0, 2, 0, 4, 3, 3, 3, 1]$. The concatenation of sequences $p$ and $q$ is denoted as $p+q$. 24 25 Gyeonggeun thinks that sequences with ascents bring luck. Therefore, he wants to make many such sequences for the new year. Gyeonggeun has $n$ sequences $s_1, s_2, \ldots, s_n$ which may have different lengths. 26 27 Gyeonggeun will consider all $n^2$ pairs of sequences $s_x$ and $s_y$ ($1 \le x, y \le n$), and will check if its concatenation $s_x + s_y$ has an ascent. Note that he may select the same sequence twice, and the order of selection matters. 28 29 Please count the number of pairs ($x, y$) of sequences $s_1, s_2, \ldots, s_n$ whose concatenation $s_x + s_y$ contains an ascent. 30 31 Input 32 33 The first line contains the number $n$ ($1 \le n \le 100\,000$) denoting the number of sequences. 34 35 The next $n$ lines contain the number $l_i$ ($1 \le l_i$) denoting the length of $s_i$, followed by $l_i$ integers $s_{i, 1}, s_{i, 2}, \ldots, s_{i, l_i}$ ($0 \le s_{i, j} \le 10^6$) denoting the sequence $s_i$. 36 37 It is guaranteed that the sum of all $l_i$ does not exceed $100\,000$. 38 39 Output 40 41 Print a single integer, the number of pairs of sequences whose concatenation has an ascent. 42 43 Examples 44 45 Input 46 47 ``` 48 5 49 1 1 50 1 1 51 1 2 52 1 4 53 1 3 54 ``` 55 56 Output 57 58 ``` 59 9 60 ``` 61 62 Input 63 64 ``` 65 3 66 4 2 0 2 0 67 6 9 9 8 8 7 7 68 1 6 69 ``` 70 71 Output 72 73 ``` 74 7 75 ``` 76 77 Input 78 79 ``` 80 10 81 3 62 24 39 82 1 17 83 1 99 84 1 60 85 1 64 86 1 30 87 2 79 29 88 2 20 73 89 2 85 37 90 1 100 91 ``` 92 93 Output 94 95 ``` 96 72 97 ``` 98 99 Note 100 101 For the first example, the following $9$ arrays have an ascent: $[1, 2], [1, 2], [1, 3], [1, 3], [1, 4], [1, 4], [2, 3], [2, 4], [3, 4]$. Arrays with the same contents are counted as their occurences.