Smartphone Addiction

AtCoder

IDabc185_b

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

10 2 20
9 11
13 17

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`.

Input #2

10 2 20
9 11
13 16

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`.

Input #3

Output #3

Yes

The battery charge drops to $1$ mAh when he gets home, but it never drops to $0$ on the way.

Input #4

20 1 30
20 29

Output #4

No

The battery charge drops to $0$ at time $19.5$.

Input #5

20 1 30
1 10

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.

API Response (JSON)

{
  "problem": {
    "name": "Smartphone Addiction",
    "description": {
      "content": "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.   Takaha",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc185_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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.  \nTakaha...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments