codeforces-scrape

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

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.