102724: [AtCoder]ABC272 E - Add and Mex
Description
Score : $500$ points
Problem Statement
You are given an integer sequence $A=(A_1,A_2,\ldots,A_N)$ of length $N$.
Perform the following operation $M$ times:
- For each $i\ (1\leq i \leq N)$, add $i$ to $A_i$. Then, find the minimum non-negative integer not contained in $A$.
Constraints
- $1\leq N,M \leq 2\times 10^5$
- $-10^9\leq A_i\leq 10^9$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$
Output
Print $M$ lines.
The $i$-th $(1\leq i \leq M)$ line should contain the minimum non-negative integer not contained in $A$ after the $i$-th operation.
Sample Input 1
3 3 -1 -1 -6
Sample Output 1
2 2 0
The $1$-st operation makes the sequence $A$
$(-1 + 1, -1 +2 ,-6+3) = (0,1,-3).$
The minimum non-negative integer not contained in $A$ is $2$.
The $2$-nd operation makes the sequence $A$
$(0 + 1, 1 +2 ,-3+3) = (1,3,0).$
The minimum non-negative integer not contained in $A$ is $2$.
The $3$-rd operation makes the sequence $A$
$(1 + 1, 3 +2 ,0+3) = (2,5,3).$
The minimum non-negative integer not contained in $A$ is $0$.
Sample Input 2
5 6 -2 -2 -5 -7 -15
Sample Output 2
1 3 2 0 0 0
Input
题意翻译
你有一个长度为 $ N $ 的整数数列 $ A $,然后进行 $ M $ 次以下操作: + 将每个数 $ A_i $ 增加 $ i $。然后求数列 $ A $ 中没有的最小的非负整数。Output
问题描述
你被给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$。
执行以下 $M$ 次操作:
- 对于每个 $i\ (1\leq i \leq N)$,将 $i$ 添加到 $A_i$。 然后,找到不包含在 $A$ 中的最小非负整数。
约束条件
- $1\leq N,M \leq 2\times 10^5$
- $-10^9\leq A_i\leq 10^9$
- 输入中的所有值都是整数。
输入
输入从标准输入以以下格式给出:
$N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$
输出
打印 $M$ 行。
第 $i$ 行 $(1\leq i \leq M)$ 应包含第 $i$ 次操作后不包含在 $A$ 中的最小非负整数。
样例输入 1
3 3 -1 -1 -6
样例输出 1
2 2 0
第 $1$ 次操作使序列 $A$ 变为
$(-1 + 1, -1 +2 ,-6+3) = (0,1,-3).$
不包含在 $A$ 中的最小非负整数是 $2$。
第 $2$ 次操作使序列 $A$ 变为
$(0 + 1, 1 +2 ,-3+3) = (1,3,0).$
不包含在 $A$ 中的最小非负整数是 $2$。
第 $3$ 次操作使序列 $A$ 变为
$(1 + 1, 3 +2 ,0+3) = (2,5,3).$
不包含在 $A$ 中的最小非负整数是 $0$。
样例输入 2
5 6 -2 -2 -5 -7 -15
样例输出 2
1 3 2 0 0 0