|
||||||||||
sceneryTime 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
Sample Output
Source | ||||||||||
|