C - Traveling

Contest Duration: 2018-01-21(Sun) 12:00 - 2018-01-21(Sun) 13:40 (local time) (100 minutes) Back to Home

C - Traveling Editorial

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : $300$ 点

問題文

シカのAtCoDeerくんは二次元平面上で旅行をしようとしています。 AtCoDeerくんの旅行プランでは、時刻 $0$ に点 $(0,0)$ を出発し、 $1$ 以上 $N$ 以下の各 $i$ に対し、時刻 $t_i$ に点 $(x_i,y_i)$ を訪れる予定です。

AtCoDeerくんが時刻 $t$ に点 $(x,y)$ にいる時、時刻 $t+1$ には点 $(x+1,y)$ , $(x-1,y)$ , $(x,y+1)$ , $(x,y-1)$ のうちいずれかに存在することができます。 その場にとどまることは出来ないことに注意してください。 AtCoDeerくんの旅行プランが実行可能かどうか判定してください。

制約

$1$ $≤$ $N$ $≤$ $10^5$
$0$ $≤$ $x_i$ $≤$ $10^5$
$0$ $≤$ $y_i$ $≤$ $10^5$
$1$ $≤$ $t_i$ $≤$ $10^5$
$t_i$ $<$ $t_{i+1}$ ( $1$ $≤$ $i$ $≤$ $N-1$ )
入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $t_1$   $x_1$   $y_1$ 
 $t_2$   $x_2$   $y_2$ 
 $:$ 
 $t_N$   $x_N$   $y_N$

出力

旅行プランが実行可能ならYesを、不可能ならNoを出力してください。

入力例 1Copy

Copy

2
3 1 2
6 1 1

出力例 1Copy

Copy

Yes

例えば、 $(0,0)$ , $(0,1)$ , $(1,1)$ , $(1,2)$ , $(1,1)$ , $(1,0)$ , $(1,1)$ と移動すればよいです。

入力例 2Copy

Copy

1
2 100 100

出力例 2Copy

Copy

No

$(0,0)$ にいる状態から $2$ 秒後に $(100,100)$ にいるのは不可能です。

入力例 3Copy

Copy

2
5 1 1
100 1 1

出力例 3Copy

Copy

No

Score : $300$ points

Problem Statement

AtCoDeer the deer is going on a trip in a two-dimensional plane. In his plan, he will depart from point $(0, 0)$ at time $0$ , then for each $i$ between $1$ and $N$ (inclusive), he will visit point $(x_i,y_i)$ at time $t_i$ .

If AtCoDeer is at point $(x, y)$ at time $t$ , he can be at one of the following points at time $t+1$ : $(x+1,y)$ , $(x-1,y)$ , $(x,y+1)$ and $(x,y-1)$ . Note that he cannot stay at his place. Determine whether he can carry out his plan.

Constraints

$1$ $≤$ $N$ $≤$ $10^5$
$0$ $≤$ $x_i$ $≤$ $10^5$
$0$ $≤$ $y_i$ $≤$ $10^5$
$1$ $≤$ $t_i$ $≤$ $10^5$
$t_i$ $<$ $t_{i+1}$ ( $1$ $≤$ $i$ $≤$ $N-1$ )
All input values are integers.

Input

Input is given from Standard Input in the following format:

 $N$ 
 $t_1$   $x_1$   $y_1$ 
 $t_2$   $x_2$   $y_2$ 
 $:$ 
 $t_N$   $x_N$   $y_N$

Output

If AtCoDeer can carry out his plan, print Yes; if he cannot, print No.

Sample Input 1Copy

Copy

2
3 1 2
6 1 1

Sample Output 1Copy

Copy

Yes

For example, he can travel as follows: $(0,0)$ , $(0,1)$ , $(1,1)$ , $(1,2)$ , $(1,1)$ , $(1,0)$ , then $(1,1)$ .

Sample Input 2Copy

Copy

1
2 100 100

Sample Output 2Copy

Copy

No

It is impossible to be at $(100,100)$ two seconds after being at $(0,0)$ .

Sample Input 3Copy

Copy

2
5 1 1
100 1 1

Sample Output 3Copy

Copy

No