Codeforces Round 968 (Div. 2) |
---|
Finished |
This is an easy version of this problem. The differences between the versions are the constraint on $$$m$$$ and $$$r_i < l_{i + 1}$$$ holds for each $$$i$$$ from $$$1$$$ to $$$m - 1$$$ in the easy version. You can make hacks only if both versions of the problem are solved.
Turtle gives you $$$m$$$ intervals $$$[l_1, r_1], [l_2, r_2], \ldots, [l_m, r_m]$$$. He thinks that a permutation $$$p$$$ is interesting if there exists an integer $$$k_i$$$ for every interval ($$$l_i \le k_i < r_i$$$), and if he lets $$$a_i = \max\limits_{j = l_i}^{k_i} p_j, b_i = \min\limits_{j = k_i + 1}^{r_i} p_j$$$ for every integer $$$i$$$ from $$$1$$$ to $$$m$$$, the following condition holds:
$$$$$$\max\limits_{i = 1}^m a_i < \min\limits_{i = 1}^m b_i$$$$$$
Turtle wants you to calculate the maximum number of inversions of all interesting permutations of length $$$n$$$, or tell him if there is no interesting permutation.
An inversion of a permutation $$$p$$$ is a pair of integers $$$(i, j)$$$ ($$$1 \le i < j \le n$$$) such that $$$p_i > p_j$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$). The description of the test cases follows.
The first line of each test case contains two integers $$$n, m$$$ ($$$2 \le n \le 5 \cdot 10^3, 0 \le m \le \frac{n}{2}$$$) — the length of the permutation and the number of intervals.
The $$$i$$$-th of the following $$$m$$$ lines contains two integers $$$l_i, r_i$$$ ($$$1 \le l_i < r_i \le n$$$) — the $$$i$$$-th interval.
Additional constraint on the input in this version: $$$r_i < l_{i + 1}$$$ holds for each $$$i$$$ from $$$1$$$ to $$$m - 1$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^3$$$.
For each test case, if there is no interesting permutation, output a single integer $$$-1$$$.
Otherwise, output a single integer — the maximum number of inversions.
62 02 11 25 12 48 21 46 87 21 34 77 31 23 45 6
1 0 8 21 15 15
In the third test case, the interesting permutation with the maximum number of inversions is $$$[5, 2, 4, 3, 1]$$$.
In the fourth test case, the interesting permutation with the maximum number of inversions is $$$[4, 8, 7, 6, 3, 2, 1, 5]$$$. In this case, we can let $$$[k_1, k_2] = [1, 7]$$$.
In the fifth test case, the interesting permutation with the maximum number of inversions is $$$[4, 7, 6, 3, 2, 1, 5]$$$.
In the sixth test case, the interesting permutation with the maximum number of inversions is $$$[4, 7, 3, 6, 2, 5, 1]$$$.
Name |
---|