F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

scenery

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 449    Accepted Submission(s): 156


Problem Description
你正在一处景点取景,你找到了 $n$ 处有趣的景色并打算给每处景色拍一张照片。一天可以被分为 $m$ 个时间段,你发现第 $i$ 处景色只有在一天中的第 $l_i \sim r_i$ 个时间段才能被拍摄到,并且拍摄这处景色需要消耗连续的 $t_i$ 个时间段(即需要选连续的 $t_i$ 个时间段用于拍摄景色 $i$,且所有选出的时间段需要在 $[l_i,r_i]$ 内)。你同一时间段只能拍摄一处景色,问能否顺利拍摄完所有 $n$ 处景色?

**保证 $l$ 序列不增,$r$ 序列不降。**
 

Input
本题有多组数据。第一行一个正整数 $T$($1\le T\le 2\times 10^3$),表示测试数据组数。

对于每组数据,第一行两个整数 $n,m$($1 \le n,m \le 5000$)。

接下来 $n$ 行,每行三个整数 $l_i,r_i,t_i$($1 \le l_i \le r_i \le m,1 \le t_i \le m$)。

保证 $\forall 1 < i \le n,l_i \le l_{i-1},r_i \ge r_{i-1}$。

保证 $\sum n^2$ 和 $\sum m^2$ 均不超过 $10000^2$。
 

Output
对于每组数据,如果能顺利拍摄所有 $n$ 处景色输出 `YES`,否则输出 `NO`。
 

Sample Input
5 5 12 4 6 2 3 9 2 1 11 3 1 11 1 1 12 2 6 8 4 5 1 4 6 1 4 6 3 2 6 1 1 7 1 1 7 2 4 10 5 7 1 4 7 1 1 9 2 1 10 3 3 5 3 3 3 2 3 1 2 5 1 4 12 5 7 1 3 10 2 2 11 3 1 11 1
 

Sample Output
YES NO YES NO YES
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-11-25 04:13:12, Gzip enabled