/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
長さ N の整数からなる数列 A=(A_1,\ldots,A_N),B=(B_1,\ldots,B_N) が与えられます。
以下の条件を全て満たす長さ N の数列 X=(X_1,\ldots,X_N) が存在するかを判定してください。
-
すべての i(1\leq i\leq N) について、X_i = A_i または X_i = B_i
-
すべての i(1\leq i\leq N-1) について、|X_i - X_{i+1}| \leq K
制約
- 1 \leq N \leq 2\times 10^5
- 0 \leq K \leq 10^9
- 1 \leq A_i,B_i \leq 10^9
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 \ldots A_N B_1 \ldots B_N
出力
条件を全て満たす X が存在するならば Yes と、存在しないならば No と出力せよ。
入力例 1
5 4 9 8 3 7 2 1 6 2 9 5
出力例 1
Yes
X=(9,6,3,7,5) が全ての条件を満たします。
入力例 2
4 90 1 1 1 100 1 2 3 100
出力例 2
No
条件を満たす X は存在しません。
入力例 3
4 1000000000 1 1 1000000000 1000000000 1 1000000000 1 1000000000
出力例 3
Yes
Score : 300 points
Problem Statement
You are given two sequences, each of length N, consisting of integers: A=(A_1, \ldots, A_N) and B=(B_1, \ldots, B_N).
Determine whether there is a sequence of length N, X=(X_1, \ldots, X_N), satisfying all of the conditions below.
-
X_i = A_i or X_i = B_i, for every i(1\leq i\leq N).
-
|X_i - X_{i+1}| \leq K, for every i(1\leq i\leq N-1).
Constraints
- 1 \leq N \leq 2\times 10^5
- 0 \leq K \leq 10^9
- 1 \leq A_i,B_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K A_1 \ldots A_N B_1 \ldots B_N
Output
If there is an X that satisfies all of the conditions, print Yes; otherwise, print No.
Sample Input 1
5 4 9 8 3 7 2 1 6 2 9 5
Sample Output 1
Yes
X=(9,6,3,7,5) satisfies all conditions.
Sample Input 2
4 90 1 1 1 100 1 2 3 100
Sample Output 2
No
No X satisfies all conditions.
Sample Input 3
4 1000000000 1 1 1000000000 1000000000 1 1000000000 1 1000000000
Sample Output 3
Yes