← 返回题目列表

Codeforces · 1889/C1

C1. 多蕾米的晒衣计划(简易版)

中文机器翻译题面 查看原题

这个问题的两个版本之间的唯一区别是 $$$k$$$ 的约束、时间限制和内存限制。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。

Doremy 生活在一个多雨的国家,由 $$$n$$$ 个城市组成,编号从 $$$1$$$ 到 $$$n$$$。

天气预报预测了未来 $$$m$$$ 天的降雨分布。第$$$i$$$天,$$$[l_i, r_i]$$$区间内的城市将下雨。如果一个城市在接下来的 $$$m$$$ 天内永远不会下雨,则该城市被称为干燥城市。

原来多蕾米拥有一种特殊的力量。她可以选择 $$$k$$$ 天(在简单版本中,$$$k = 2$$$),在这些天里不会下雨。多雷米想要计算出使用特殊力量后最多能有多少个干旱城市。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1\le n\le 2\cdot 10^5$$$, $$$2 \le m \le 2\cdot 10^5$$$, $$$k = 2$$$) — 城市数量、天数、多蕾米可以阻止的雨。

然后是 $$$m$$$ 行。第 $$$i$$$ 行包含两个整数 $$$l_i$$$、$$$r_i$$$ ($$$1\le l_i\le r_i\le n$$$) — $$$i$$$ 天的降雨覆盖范围。

保证所有测试用例的 $$$n$$$ 之和与 $$$m$$$ 之和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数——干旱城市的最大数量。

示例

输入 #1

6
2 3 2
1 2
1 2
1 1
5 3 2
1 3
2 4
3 5
10 6 2
1 5
6 10
2 2
3 7
5 8
1 4
100 6 2
1 100
1 100
1 100
1 100
1 100
1 100
1000 2 2
1 1
1 1
20 5 2
9 20
3 3
10 11
11 13
6 18

输出 #1

1
2
3
0
1000
15

注意

在第一个测试用例中,如果 Doremy 阻止

- 下雨$$$1,2$$$,然后城市$$$2$$$将会干燥;
- 下雨$$$2,3$$$,那么没有城市会干燥;
- 下雨$$$1,3$$$,那么没有城市会干燥;

所以最多有 $$$1$$$ 干燥城市。

在第二个测试用例中,如果 Doremy 阻止

- 下雨$$$1,2$$$,然后城市$$$1,2$$$将会干燥;
- 下雨$$$2,3$$$,然后城市$$$4,5$$$将会干燥;
- 下雨$$$1,3$$$,然后城市$$$1,5$$$将会干燥。

所以最多有 $$$2$$$ 干旱城市。

在第三个测试用例中,最好防止下雨 $$$2,5$$$。

在第四个测试用例中,总是有 $$$4$$$ 天的降雨,湿润了所有城市并且无法阻止。