102696: [AtCoder]ABC269 G - Reversible Cards 2

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $600$ points

Problem Statement

We have $N$ cards numbered $1$ to $N$.
Card $i$ has an integer $A_i$ written on the front and an integer $B_i$ written on the back. Here, $\sum_{i=1}^N (A_i + B_i) = M$.
For each $k=0,1,2,...,M$, solve the following problem.

The $N$ cards are arranged so that their front sides are visible. You may choose between $0$ and $N$ cards (inclusive) and flip them.
To make the sum of the visible numbers equal to $k$, at least how many cards must be flipped? Print this number of cards.
If there is no way to flip cards to make the sum of the visible numbers equal to $k$, print $-1$ instead.

Constraints

  • $1 \leq N \leq 2 \times 10^5$
  • $0 \leq M \leq 2 \times 10^5$
  • $0 \leq A_i, B_i \leq M$
  • $\sum_{i=1}^N (A_i + B_i) = M$
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$ 
$A_N$ $B_N$

Output

Print $M+1$ lines. The $i$-th line should contain the answer for $k=i-1$.


Sample Input 1

3 6
0 2
1 0
0 3

Sample Output 1

1
0
2
1
1
3
2

For $k=0$, for instance, flipping just card $2$ makes the sum of the visible numbers $0+0+0=0$. This choice is optimal.
For $k=5$, flipping all cards makes the sum of the visible numbers $2+0+3=5$. This choice is optimal.


Sample Input 2

2 3
1 1
0 1

Sample Output 2

-1
0
1
-1

Sample Input 3

5 12
0 1
0 3
1 0
0 5
0 2

Sample Output 3

1
0
1
1
1
2
1
2
2
2
3
3
4

Input

题意翻译

有 $n$ 张卡片,第 $i$ 张卡片正面有数字 $a_i$,背面有数字 $b_i$,同时 $\sum_{i=1}^n (a_i+b_i)=m$。所有卡片起初均被正面朝上地放置。 对于 $\forall k\in[0,m]$,输出使得所有卡片朝上的数字之和为 $k$ 时,需要翻面至少多少张卡片;如果不能通过翻面卡片使得所有卡片朝上的数字之和为 $k$ 则输出 $-1$。 $1\le n\le 2\times 10^5,0\le m\le 2\times 10^5,0\le a_i,b_i\le m$。

Output

分数:$600$分

问题描述

我们有$N$张编号为$1$到$N$的卡片。
卡片$i$的正面写着一个整数$A_i$,背面写着一个整数$B_i$。这里,$\sum_{i=1}^N (A_i + B_i) = M$。
对于每个$k=0,1,2,...,M$,解决以下问题。

将这$N$张卡片排列,使它们的正面可见。你可以选择$0$到$N$张卡片(包括)并翻转它们。
要使可见数字的和等于$k$,至少需要翻转多少张卡片?打印这个卡片数量。
如果无法翻转卡片使可见数字的和等于$k$,则打印$-1$。

约束条件

  • $1 \leq N \leq 2 \times 10^5$
  • $0 \leq M \leq 2 \times 10^5$
  • $0 \leq A_i, B_i \leq M$
  • $\sum_{i=1}^N (A_i + B_i) = M$
  • 输入中的所有值都是整数。

输入

输入以标准输入的以下格式给出:

$N$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$ 
$A_N$ $B_N$

输出

打印$M+1$行。第$i$行应该包含对于$k=i-1$的答案。


样例输入 1

3 6
0 2
1 0
0 3

样例输出 1

1
0
2
1
1
3
2

例如,对于$k=0$,仅翻转卡片$2$使得可见数字的和为$0+0+0=0$。这个选择是最佳的。
对于$k=5$,翻转所有卡片使得可见数字的和为$2+0+3=5$。这个选择是最佳的。


样例输入 2

2 3
1 1
0 1

样例输出 2

-1
0
1
-1

样例输入 3

5 12
0 1
0 3
1 0
0 5
0 2

样例输出 3

1
0
1
1
1
2
1
2
2
2
3
3
4

加入题单

上一题 下一题 算法标签: