← 返回题目列表

Codeforces · 1304/C

C. 空调

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

Gildong 拥有一家烤肉餐厅。这家餐厅的顾客很多,所以很多人都喜欢在来之前先预约。

Gildong非常努力地满足顾客,他甚至记住了所有顾客喜欢的温度范围!翻看预订单,他想通过控制餐厅的温度来满足所有顾客的需求。

餐厅的空调有 3 种状态:关闭、制热和制冷。当关闭时,餐厅的温度保持不变。加热时,温度在一分钟内升高1。最后,冷却时,温度在一分钟内降低1。 Gildong 可以在任意整数分钟内根据需要多次更改状态。空调一开始是关闭的。

每个顾客都由三个值来表征:$$$t_i$$$ — 第 $$$i$$$ 顾客访问餐厅的时间​​(以分钟为单位),$$$l_i$$$ — 他们首选温度范围的下限,以及 $$$h_i$$$ — 他们首选温度范围的上限。

如果顾客在访问餐厅时温度处于首选范围内,他们会感到满意。形式上,当且仅当第 $$$t_i$$$ 分钟内的温度在 $$$l_i$$$ 和 $$$h_i$$$(含)之间时,第 $$$i$$$ 客户才满意。

给定初始温度、预订客户的访问时间列表以及他们的首选温度范围,您将帮助他找到是否可以满足所有客户。

输入

每个测试都包含一个或多个测试用例。第一行包含测试用例的数量 $$$q$$$ ($$$1 \le q \le 500$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数$$$n$$$和$$$m$$$($$$1 \le n \le 100$$$, $$$-10^9 \le m \le 10^9$$$),其中$$$n$$$是预订顾客的数量,$$$m$$$是餐厅的初始温度。

接下来是 $$$n$$$ 行。其中第 $$$i$$$ 行包含三个整数 $$$t_i$$$、$$$l_i$$$ 和 $$$h_i$$$ ($$$1 \le t_i \le 10^9$$$, $$$-10^9 \le l_i \le h_i \le 10^9$$$),其中 $$$t_i$$$ 是第 $$$i$$$ 次客户访问,$$$l_i$$$ 是他们首选温度范围的下限,$$$h_i$$$ 是他们首选温度范围的上限。优选的温度范围包括在内。

客户按访问时间非递减顺序给出,当前时间为$$$0$$$。

输出

对于每个测试用例,如果可以满足所有客户,请打印“YES”。否则,打印“NO”。

您可以以任何大小写(大写或小写)打印每个字母。

示例

输入 #1

4
3 0
5 1 2
7 3 5
10 -1 0
2 12
5 7 10
10 16 20
3 -100
100 0 0
100 -50 50
200 100 100
1 100
99 -100 0

输出 #1

YES
NO
YES
NO

注意

在第一种情况下,Gildong可以通过以下方式控制空调以满足所有客户:

- 在第 $$$0$$$ 分钟,将状态更改为加热(温度为 0)。
- 在第$$$2$$$第分钟,将状态更改为关闭(温度为2)。
- 在第$$$5$$$分钟,将状态更改为加热(温度为2,第$$$1$$$顾客满意)。
- 在第 $$$6$$$ 分钟,将状态更改为关闭(温度为 3)。
- 在第$$$7$$$分钟,将状态更改为冷却(温度为3,第$$$2$$$客户满意)。
- 在第 $$$10$$$ 分钟时,温度将为 0,这满足了最后一位顾客的要求。

在第三种情况下,Gildong 可以在第 $$$0$$$ 分钟将状态更改为加热状态并保持不变。那么所有的顾客都会满意。请注意,$$$1$$$-st 客户的访问时间等于 $$$2$$$-nd 客户的访问时间。

在第二个和第四个案例中,Gildong 必须让至少一名顾客不满意。