← 返回题目列表

Codeforces · 1999/C

C. 淋浴

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

作为一名计算机科学专业的学生,​​亚历克斯面临着一项艰巨的挑战——洗澡。他尝试每天洗澡,但尽管他尽了最大努力,但总是遇到挑战。他洗澡需要 $$$s$$$ 分钟,而一天只有 $$$m$$$ 分钟!

他当天已经计划了 $$$n$$$ 任务。任务 $$$i$$$ 表示为一个时间间隔 $$$(l_i$$$, $$$r_i)$$$,这意味着 Alex 很忙,无法在该时间间隔内洗澡(严格在 $$$l_i$$$ 和 $$$r_i$$$ 之间的任何时间点)。没有两个任务重叠。

考虑到所有 $$$n$$$ 时间间隔,Alex 那天能够洗澡吗?换句话说,Alex 是否有至少 $$$s$$$ 长度的空闲时间间隔?

在第一个测试用例中,Alex 可以在当天的前 $$$3$$$ 分钟洗澡,并且不会错过任何任务。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$s$$$ 和 $$$m$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$; $$$1 \leq s, m \leq 10^9$$$) - Alex 已经计划的时间间隔数,Alex 采取一个淋浴,以及每天的分钟数。

接下来是 $$$n$$$ 行,其中第 $$$i$$$ 包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$0 \leq l_i < r_i \leq m$$$) — 第 $$$i$$$ 个任务的时间间隔。没有两个任务重叠。

对输入的附加约束:对于每个 $$$i > 1$$$,$$$l_i > r_{i-1}$$$。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果 Alex 可以为给定的测试用例洗澡,则输出“YES”(不带引号),否则输出“NO”(也不带引号)。

在任何情况下都可以输出“YES”和“NO”(例如,字符串“yEs”、“yes”和“Yes”将被识别为肯定响应)。

示例

输入 #1

4
3 3 10
3 5
6 8
9 10
3 3 10
1 2
3 5
6 7
3 3 10
1 2
3 5
6 8
3 4 10
1 2
6 7
8 9

输出 #1

YES
YES
NO
YES