← 返回题目列表

AtCoder · agc047_f

F. 车

中文机器翻译题面 查看原题

分数: 2200 点

问题陈述

您已获得职位 (X_i, Y_i) of N 无限棋盘上的敌方车。 没有两只车会互相攻击(每行或每列最多有一只车)。

你要用一张王替换一张车,然后反复移动王以击败尽可能多的车。

你无法进入正在被车攻击的牢房。 另外,你 无法对角移动到空单元格 (但你可以对角击败车)。

(所以这个国王的移动就像一个超级棋子,在 4 个方向上对角地跳动,并在 4 个方向上水平/垂直移动。)

对于每个车,考虑用国王替换它,并找到最小可能的移动数 需要击败尽可能多的车。

约束

  • 2 \leq N \leq 200\,000
  • 1 \leq X_i, Y_i \leq 10^6
  • X_i \neq X_j
  • Y_i \neq Y_j
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出。

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

输出

打印 N 行。 的 i-第行用于更换车的场景 (X_i, Y_i) 与你的国王。 这一行应包含一个整数:要击败的最小步数 M_i 车 哪里 M_i 表示在这种情况下(无限时间内)被击败的车的最大可能数量。


示例输入 1

6
1 8
6 10
2 7
4 4
9 3
5 1

示例输出 1

5
0
7
5
0
0

参见下图。 如果我们用国王替换车 3,我们最多可以击败另外两个车。 红色路径是最佳的移动序列之一:击败车 1, 然后继续向下和向右,直到你可以击败车 4。 有 7 个步骤,这是输出中的第三个数字。

path

x 坐标从左到右增加, 而 y 从下到上增加。

从2号、5号或6号车开始,我们无法击败任何其他车。 最佳移动次数为 0。


示例输入 2

5
5 5
100 100
70 20
81 70
800 1

示例输出 2

985
985
1065
1034
0

示例输入 3

10
2 5
4 4
13 12
12 13
14 17
17 19
22 22
16 18
19 27
25 26

示例输出 3

2
2
9
9
3
3
24
5
0
25