102452: [AtCoder]ABC245 C - Choose Elements
Description
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
Input
题意翻译
给出两个由整数组成的序列 $A = (A_1,\ldots, A_N)$,$B = (B_1,\ldots, B_N)$ 求满足以下所有条件的长度 $N$ 的序列 $X=(X_1,\ldots,X_N)$ 否存在 - 所有的 $i$ $(1≤i≤N)$ 满足 $X_i = A_i$ 或 $X_i = B_i$ - 所有的 $i$ $(1≤i≤N)$ 满足 $|X_i - X_{i+1}|≤ K$Output
问题描述
你有两个长度为$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