/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
給湯器が 1 つあり、毎分 W リットルのお湯を供給することができます。
N 人の人がいます。i 番目の人は時刻 S_i から T_i までの間 (時刻 T_i ちょうどを除く)、この湯沸かし器で沸かしたお湯を毎分 P_i リットル使おうと計画しています。お湯はすぐ冷めてしまうので、溜めておくことはできません。
すべての人に計画通りにお湯を供給することはできますか？
制約
- 1\leq N \leq 2\times 10^5
- 0\leq S_i < T_i \leq 2\times 10^5
- 1\leq W, P_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N W S_1 T_1 P_1 \vdots S_N T_N P_N
出力
すべての人に計画通りにお湯を供給することができるなら Yesを、できないなら Noを出力せよ。
入力例 1
4 10 1 3 5 2 4 4 3 10 6 2 4 1
出力例 1
No
時刻 3 から 4 の間に、2,3,4 番目の人がそれぞれ 毎分 4,6,1 リットル、合計毎分 11 リットルのお湯を使おうとしています。
給湯器は毎分 10 リットルしかお湯を供給することができないので、計画通りに供給することはできません。
入力例 2
4 10 1 3 5 2 4 4 3 10 6 2 3 1
出力例 2
Yes
入力例 3
6 1000000000 0 200000 999999999 2 20 1 20 200 1 200 2000 1 2000 20000 1 20000 200000 1
出力例 3
Yes
Score : 400 points
Problem Statement
We have a water heater, which supplies W liters of hot water per minute.
There are N people. The i-th person plans to use P_i liters of hot water per minute boiled by the heater from Time S_i to T_i (excluding at Time T_i exactly). As hot water gets cold fast, it cannot be stored.
Is it possible to supply hot water to the people according to their plans?
Constraints
- 1\leq N \leq 2\times 10^5
- 0\leq S_i < T_i \leq 2\times 10^5
- 1\leq W, P_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N W S_1 T_1 P_1 \vdots S_N T_N P_N
Output
If it is possible to supply hot water to the people according to their plans, print Yes; otherwise, print No.
Sample Input 1
4 10 1 3 5 2 4 4 3 10 6 2 4 1
Sample Output 1
No
Between Time 3 and 4, the 2-nd, 3-rd, and 4-th persons plan to use 4, 6, and 1 liter(s) of hot water per minute, for a total of 11 liters per minute.
The water heater can only supply 10 liters of hot water per minute, which is not enough.
Sample Input 2
4 10 1 3 5 2 4 4 3 10 6 2 3 1
Sample Output 2
Yes
Sample Input 3
6 1000000000 0 200000 999999999 2 20 1 20 200 1 200 2000 1 2000 20000 1 20000 200000 1
Sample Output 3
Yes