/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
高橋君のスマートフォンのバッテリー容量は N [mAh] であり、時刻 0.5, 1.5, 2.5, \ldots に、つまり時刻 n + 0.5\,(n は整数) を迎える度にバッテリー残量が 1 [mAh] ずつ減少します。
高橋君はスマートフォンを満充電した状態で時刻 0 に外出し、途中で M 回カフェを訪れ、時刻 T に帰宅します。
i 回目に訪れるカフェには時刻 A_i から時刻 B_i まで滞在します。カフェに滞在している間はスマートフォンを充電するため、バッテリー残量は減少せず、代わりに時刻 n + 0.5\,(n は整数) を迎える度に 1 [mAh] ずつ増加します。ただし既にバッテリー残量がバッテリー容量と等しい場合、バッテリー残量は増えも減りもしません。
高橋君が途中でスマートフォンのバッテリー残量が 0 になることなく帰宅することができるかを判定してください。
制約
- 1 \le N \le 10^9
- 1 \le M \le 1000
- 1 \le T \le 10^9
- 0 \lt A_1 \lt B_1 \lt A_2 \lt B_2 \lt A_3 \lt B_3 \lt \dots \lt A_M \lt B_M \lt T
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M T
A_1 B_1
A_2 B_2
A_3 B_3
\hspace{15pt} \vdots
A_M B_M
出力
高橋君が途中でスマートフォンのバッテリー残量が 0 になることなく帰宅することができるなら Yes を、できないなら No を出力せよ。
入力例 1
10 2 20 9 11 13 17
出力例 1
Yes
バッテリー残量は以下のように変化します。
- 時刻 0 (出発時): 10 [mAh]
- 時刻 9 (1 番目のカフェへの滞在開始時): 1 [mAh]
- 時刻 11 (1 番目のカフェへの滞在終了時): 3 [mAh] (カフェでは充電を行います)
- 時刻 13 (2 番目のカフェへの滞在開始時): 1 [mAh]
- 時刻 17 (2 番目のカフェへの滞在終了時): 5 [mAh]
- 時刻 20 (帰宅時): 2 [mAh]
この過程で一度もバッテリー残量が 0 になっていないので、Yes を出力します。
入力例 2
10 2 20 9 11 13 16
出力例 2
No
2 番目のカフェへの滞在をバッテリー残量 1 [mAh] の状態で開始するところまでは入出力例 1 と同じです。
時刻 16 に 2 番目のカフェの滞在を終了したときのバッテリー残量は 4 [mAh] になります。
そして時刻 19.5 にバッテリー残量が 0 になってしまうので、No を出力します。
入力例 3
15 3 30 5 8 15 17 24 27
出力例 3
Yes
帰宅するときにはバッテリー残量が 1 [mAh] になっていますが、 1 度も 0 にはなっていません。
入力例 4
20 1 30 20 29
出力例 4
No
時刻 19.5 でバッテリー残量が 0 になります。
入力例 5
20 1 30 1 10
出力例 5
No
バッテリー残量がバッテリー容量と等しい場合は、カフェにいてもバッテリー残量が増えないことに注意して下さい。
Score : 200 points
Problem Statement
The battery of Takahashi's smartphone has N mAh capacity. At time 0.5, 1.5, 2.5, and so on (that is, at time n + 0.5 for every integer n), the battery charge decreases by 1 mAh.
Takahashi will leave his house with his phone fully charged at time 0, visit a cafe M times, and return home at time T.
He will stay at the i-th cafe from time A_i to time B_i. During this stay, he charges his phone, so the battery charge does not decrease. Instead, at time n + 0.5 for every integer n, it increases by 1. However, if it is already equal to the battery capacity, it does not increase nor decrease.
Determine whether he can return home without the battery charge dropping to 0 on the way.
Constraints
- 1 \le N \le 10^9
- 1 \le M \le 1000
- 1 \le T \le 10^9
- 0 \lt A_1 \lt B_1 \lt A_2 \lt B_2 \lt A_3 \lt B_3 \lt \dots \lt A_M \lt B_M \lt T
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M T
A_1 B_1
A_2 B_2
A_3 B_3
\hspace{15pt} \vdots
A_M B_M
Output
If Takahashi can return home without the battery charge dropping to 0 on the way, print Yes; otherwise, print No.
Sample Input 1
10 2 20 9 11 13 17
Sample Output 1
Yes
The battery charge changes as follows:
- Time 0 (leaving home): 10 mAh
- Time 9 (the beginning of the stay at the first cafe): 1 mAh
- Time 11 (the end of the stay at the first cafe): 3 mAh (He charges his phone in a cafe.)
- Time 13 (the beginning of the stay at the second cafe): 1 mAh
- Time 17 (the end of the stay at the second cafe): 5 mAh
- Time 20 (getting home): 2 mAh
During this process, the battery charge never drops to 0, so we print Yes.
Sample Input 2
10 2 20 9 11 13 16
Sample Output 2
No
This case is the same as Sample Input/Output 1 until he starts his stay at the second cafe with 1 mAh charge.
When he ends his stay there at time 16, the battery charge is 4 mAh.
Then at time 19.5, it drops to 0, so we print No.
Sample Input 3
15 3 30 5 8 15 17 24 27
Sample Output 3
Yes
The battery charge drops to 1 mAh when he gets home, but it never drops to 0 on the way.
Sample Input 4
20 1 30 20 29
Sample Output 4
No
The battery charge drops to 0 at time 19.5.
Sample Input 5
20 1 30 1 10
Sample Output 5
No
Note that when the battery charge is equal to the battery capacity, staying at a cafe does not increase the battery charge.