New Year and Ascent Sequence
Contest: Hello 2020
Difficulty rating: 1400
Tags: binary search, combinatorics, data structures, dp, implementation, sortings

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 < j \le l$$$ and $$$a_i < 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.

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

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.

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.

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.

Input format:
The first line contains the number $$$n$$$ ($$$1 \le n \le 100\,000$$$) denoting the number of sequences.

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

It is guaranteed that the sum of all $$$l_i$$$ does not exceed $$$100\,000$$$.

Output format:
Print a single integer, the number of pairs of sequences whose concatenation has an ascent.

Constraints:
Time limit: 2.0 s
Memory limit: 1024.0 MB

Note:
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.

Example input:
5
1 1
1 1
1 2
1 4
1 3

Example output:
9

Example input:
3
4 2 0 2 0
6 9 9 8 8 7 7
1 6

Example output:
7

Editorial:
Define a non-increasing sequence to be a sequence where $$$a_i \ge a_{i+1}$$$ for all $$$i$$$. A sequence does not contain an ascent if and only if it is a non-increasing sequence. Thus, we want to count the number of pairs of sequence whose concatenation is not a non-increasing sequence.
If $$$c$$$ is the number of pairs whose concatenation is a non-increasing sequence, the answer is therefore $$$n^2 - c$$$. We will focus on computing $$$c$$$.
If a given sequence is not a non-increasing sequence, concatenating it with another sequence does not change this property. Thus, we will only consider merging two non-increasing sequences.
For non-increasing sequences $$$s, t$$$ to be mergeable as a non-increasing sequence, the last element of $$$s$$$ must not be smaller the first element of $$$t$$$. For all given non-increasing sequence, let's denote $$$f_i, l_j$$$ to be the first/last element of the respective sequence, we want to count the number of pairs $$$1 \le i, j\le n$$$ such that $$$l_i \geq f_j$$$.
Counting this can be done in numerous ways. One way is to sort the sequence $$$f$$$, and do a binary search for each $$$l_i$$$ to find how many elements are at most $$$l_i$$$. The time complexity of this is $$$O(n\log n)$$$.