Smartphone Addiction

题目描述

Takahashi 的智能手机电池容量为 $N$ mAh。 在时间 $0.5$、$1.5$、$2.5$ 等等（即对于每个整数 $n$，在时间 $n + 0.5$），电池电量会减少 $1$ mAh。
Takahashi 会在时间 $0$ 手机充满电离开家，访问咖啡馆 $M$ 次，并在时间 $T$ 回家。
他将在第 $i$ 次咖啡馆停留从时间 $A_i$ 到时间 $B_i$。在此停留期间，他为手机充电，所以电池电量不会减少。相反地，对于每个整数 $n$，在时间 $n + 0.5$，电量会增加 $1$。但是，如果电量已经等于电池容量，则既不会增加也不会减少。
判断他能否在路上返回家而电池电量不降到 $0$。

输入格式

输入从标准输入按如下格式给出： $N$ $M$ $T$ $A_1$ $B_1$ $A_2$ $B_2$ $A_3$ $B_3$ $\hspace{15pt} \vdots$ $A_M$ $B_M$

输出格式

如果 Takahashi 能在路上返回家而电池电量不降到 $0$，则输出 $Yes$；否则输出 $No$。

10 2 20
9 11
13 17

Yes

10 2 20
9 11
13 16

No

15 3 30
5 8
15 17
24 27

Yes

20 1 30
20 29

No

20 1 30
1 10

No

提示

$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$ 输入中的所有值均为整数。电池电量变化如下：

时间 $0$（离家时）：$10$ mAh 时间 $9$（在第一个咖啡馆开始停留时）：$1$ mAh 时间 $11$（在第一个咖啡馆结束停留时）：$3$ mAh（他在咖啡馆为手机充电。） 时间 $13$（在第二个咖啡馆开始停留时）：$1$ mAh 时间 $17$（在第二个咖啡馆结束停留时）：$5$ mAh 时间 $20$（到家时）：$2$ mAh

在此过程中，电池电量从未降到 $0$，所以我们输出 $Yes$。
此情形在他在第二个咖啡馆开始停留时电量为 $1$ mAh 之前与样例输入/输出 1 相同。
当他在那里在时间 $16$ 结束停留时，电池电量为 $4$ mAh。
然后在时间 $19.5$，电量降到 $0$，所以我们输出 $No$。
电池电量在他回家时降到 $1$ mAh，但在路上从未降到 $0$。
电池电量在时间 $19.5$ 降到 $0$。
注意当电池电量等于电池容量时，在咖啡馆停留不会增加电池电量。

标签: AtCoder|abc185B

来源

AtCoder|abc185B