A6951. abc245C - Choose Elements
编程题
普及/提高-
知识点
题目描述
#### 问题陈述
给你两个长度分别为 $N$ 的序列，它们分别由整数 $A=(A_1, \ldots, A_N)$ 和 $B=(B_1, \ldots, B_N)$ 组成。
请判断是否有长度为 $N$ , $X=(X_1, \ldots, X_N)$ 的序列满足下面的所有条件。
- $X_i = A_i$ 或 $X_i = B_i$ , 对于每个 $i(1\leq i\leq N)$ .
- $|X_i - X_{i+1}| \leq K$ ，对于每个 $i(1\leq i\leq N-1)$ 。
#### 限制因素
- $1 \leq N \leq 2\times 10^5$
- $0 \leq K \leq 10^9$
- $1 \leq A_i,B_i \leq 10^9$
- 输入值均为整数。
给你两个长度分别为 $N$ 的序列，它们分别由整数 $A=(A_1, \ldots, A_N)$ 和 $B=(B_1, \ldots, B_N)$ 组成。
请判断是否有长度为 $N$ , $X=(X_1, \ldots, X_N)$ 的序列满足下面的所有条件。
- $X_i = A_i$ 或 $X_i = B_i$ , 对于每个 $i(1\leq i\leq N)$ .
- $|X_i - X_{i+1}| \leq K$ ，对于每个 $i(1\leq i\leq N-1)$ 。
#### 限制因素
- $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$
输入内容由标准输入法提供，格式如下：
$N$ $K$
$A_1$ $\ldots$ $A_N$
$B_1$ $\ldots$ $B_N$
输出格式
#### 输出
如果有一个 $X$ 满足所有条件，则打印
如果有一个 $X$ 满足所有条件，则打印
Yes；否则，打印 No。输入输出样例
输入 #1
5 4 9 8 3 7 2 1 6 2 9 5
输出 #1
Yes
输入 #2
4 90 1 1 1 100 1 2 3 100
输出 #2
No
输入 #3
4 1000000000 1 1 1000000000 1000000000 1 1000000000 1 1000000000
输出 #3
Yes
说明/提示
### 样例一解释
$X=(9,6,3,7,5)$ 满足所有条件。
$X=(9,6,3,7,5)$ 满足所有条件。