A Pie for a Pie

题目描述

Bessie 和 Elsie 各自烤了 $N$ 个派（$1 \leq N \leq 10^5$）。这 $2N$ 个派中的每一个，都有一个“在 Bessie 眼中”的美味值，以及一个（可能不同的）“在 Elsie 眼中”的美味值。 Bessie 正在考虑送给 Elsie 一个她的派。如果 Elsie 收到 Bessie 的一个派，她会觉得有义务回赠 Bessie 一个她的派。为了既不显得小气也不显得浮夸，Elsie 会尝试挑选一个派：在 Elsie 眼中，其美味值至少与她收到的派一样，但最多只比它好吃 $D$ 个单位（$0 \leq D \leq 10^9$）。这样的派可能不存在；如果不存在，Elsie 就会改名并流放自己去日本。 但如果 Elsie 确实回赠了 Bessie 一个派，Bessie 也会类似地尝试送给 Elsie 一个派：在 Bessie 眼中，其美味值至少与 Elsie 刚送给她的派一样，但最多只比它好吃 $D$ 个单位。若这不可能，Bessie 也会流放自己。否则她会把选中的派送给 Elsie。这个循环会一直持续，直到其中一头牛被流放（不幸的结局），或者某头牛收到一个她赋予美味值为 $0$ 的派，此时赠礼交换结束，两头牛都会很开心。 注意：一个派不能被赠送两次，并且任意一头牛都不能把收到的派再回赠出去。 对于 Bessie 可能选择作为初始赠礼送给 Elsie 的 $N$ 个派中的每一个，求在随后的交换过程中、两头牛变得开心之前，可能被赠送的派的最小数量。

输入格式

第一行包含两个整数 $N$ 和 $D$。 接下来的 $2N$ 行每行包含两个用空格分隔的整数，分别表示某个派在 Bessie 眼中的价值，以及该派在 Elsie 眼中的价值。 前 $N$ 行对应 Bessie 的派，后 $N$ 行对应 Elsie 的派。 保证所有美味值都在区间 $[0,10^9]$ 内。

输出格式

输出应包含 $N$ 行。第 $i$ 行应包含一个整数：以 Bessie 的第 $i$ 个派作为初始赠礼开始的一次“开心”的赠礼交换中，可能被赠送的派的最小数量。如果以派 $i$ 开始的任何赠礼交换都无法让两头牛开心，则第 $i$ 行输出 $-1$。

2 1
1 1
5 0
4 2
1 4

3
1

提示

题目来源：Dhruv Rohatgi

标签: USACO|2017|Gold

来源

USACO|2017|Gold