New Year and Ascent Sequence (Codeforces 1284B)
Tags: Implement, combinatorics

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: 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: Print a single integer, the number of pairs of sequences whose concatenation has an ascent.

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.

Sample Inputs:
5
1 1
1 1
1 2
1 4
1 3

3
4 2 0 2 0
6 9 9 8 8 7 7
1 6

10
3 62 24 39
1 17
1 99
1 60
1 64
1 30
2 79 29
2 20 73
2 85 37
1 100

Sample Outputs:
9

7

72

Solution (Python):
n = int(input())
mini = []
maxi = []
(l, r) = (0, 0)
for i in range(n):
    sequences = list(map(int, input().split(' ')))[1:]
    for j in range(len(sequences)):
        if j > 0 and sequences[j] > sequences[j - 1]:
            l += 1
            break
        elif j == len(sequences) - 1:
            r += 1
            mini.append(min(sequences))
            maxi.append(max(sequences))
res = l * l + 2 * l * r
mini.sort()
maxi.sort()
i = 0
for x in maxi:
    while i < r and mini[i] < x:
        i += 1
    res += i
print(res)

Solution (Python):
n = int(input())
(mini, maxi, asc, nasc) = ([], [], 0, 0)
for index in range(n):
    s = list(map(int, input().split()))[1:]
    for i in range(len(s)):
        if i > 0 and s[i] > s[i - 1]:
            asc += 1
            break
        elif i == len(s) - 1:
            nasc += 1
            mini.append(min(s))
            maxi.append(max(s))
total = asc * asc + 2 * asc * nasc
mini.sort()
maxi.sort()
i = 0
for x in maxi:
    while i < nasc and mini[i] < x:
        i += 1
    total += i
print(total)

Solution (Python):
n = int(input())
(min_list, max_list, asc, nasc) = ([], [], 0, 0)
for i in range(n):
    s = list(map(int, input().split()))[1:]
    for j in range(len(s)):
        if j > 0 and s[j] > s[j - 1]:
            asc += 1
            break
        elif j == len(s) - 1:
            nasc += 1
            min_list.append(min(s))
            max_list.append(max(s))
total = asc * asc + 2 * asc * nasc
min_list.sort()
max_list.sort()
i = 0
for x in max_list:
    while i < nasc and min_list[i] < x:
        i += 1
    total += i
print(total)