CF1884C.Medium Design

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

The array $a_1, a_2, \ldots, a_m$ is initially filled with zeroes. You are given $n$ pairwise distinct segments $1 \le l_i \le r_i \le m$ . You have to select an arbitrary subset of these segments (in particular, you may select an empty set). Next, you do the following:

For each $i = 1, 2, \ldots, n$ , if the segment $(l_i, r_i)$ has been selected to the subset, then for each index $l_i \le j \le r_i$ you increase $a_j$ by $1$ (i. e. $a_j$ is replaced by $a_j + 1$ ). If the segment $(l_i, r_i)$ has not been selected, the array does not change.
Next (after processing all values of $i = 1, 2, \ldots, n$ ), you compute $\max(a)$ as the maximum value among all elements of $a$ . Analogously, compute $\min(a)$ as the minimum value.
Finally, the cost of the selected subset of segments is declared as $\max(a) - \min(a)$ .

Please, find the maximum cost among all subsets of segments.

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $t$ ( $1 \le t \le 10^4$ ). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ( $1 \le n \le 10^5$ , $1 \le m \le 10^9$ ) — the number of segments and the length of the array.

The following $n$ lines of each test case describe the segments. The $i$ -th of these lines contains two integers $l_i$ and $r_i$ ( $1 \le l_i \le r_i \le m$ ). It is guaranteed that the segments are pairwise distinct.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .

输出格式

For each test case, output the maximum cost among all subsets of the given set of segments.

输入输出样例

输入#1

6
1 3
2 2
3 8
2 4
3 5
4 6
6 3
1 1
1 2
1 3
2 2
2 3
3 3
7 6
2 2
1 6
1 2
5 6
1 5
4 4
3 6
6 27
6 26
5 17
2 3
20 21
1 22
12 24
4 1000000000
2 999999999
3 1000000000
123456789 987654321
9274 123456789

输出#1

说明/提示

In the first test case, there is only one segment available. If we do not select it, then the array will be $a = [0, 0, 0]$ , and the cost of such (empty) subset of segments will be $0$ . If, however, we select the only segment, the array will be $a = [0, 1, 0]$ , and the cost will be $1 - 0 = 1$ .

In the second test case, we can select all the segments: the array will be $a = [0, 1, 2, 3, 2, 1, 0, 0]$ in this case. The cost will be $3 - 0 = 3$ .

首页