F - Rooks

Contest Duration: 2020-08-09(Sun) 12:00 - 2020-08-09(Sun) 14:20 (local time) (140 minutes) Back to Home

F - Rooks Editorial

Time Limit: 1.25 sec / Memory Limit: 1024 MB

配点 : $2200$ 点

問題文

無限に広がるチェス盤上の $N$ 個の敵ルークの位置 $(X_i, Y_i)$ が与えられます。[訳注: ルークは将棋の飛車と似た動きをする駒です。] どの二つのルークも、お互いを攻められる位置にはありません (すなわち、一行あたり、または一列あたりのルークの数は一個以下です)。

あなたは、ルークのうち一個をキングに置き換え、キングを繰り返し動かしてできるだけ多くのルークを取ろうとしています。[訳注: キングは将棋の王将と似た動きをする駒です。]

ルークに攻められているマスに入ることはできません。また、斜めに移動することで空きマスに移ることもできません (しかし、斜めに移動することでルークを取ることはできます)。

(つまり、このキングの動きは、斜め四方向に動いて駒を取ることと縦横四方向に動くことができる強化版ポーンのようなものです。)

各ルークについて、そのルークをキングで置き換えた際に取ることのできる最大数のルークを取るために必要な最小手数を求めてください。

制約

$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$ は (何手かけてもよいとして) この場合に取ることのできるルークの最大数である。

入力例 1Copy

Copy

出力例 1Copy

Copy

下図を見てください。ルーク $3$ をキングに置き換えた場合、他のルークを最大で二個取ることができます。図の赤い経路がこの場合の最適な手順の一つ - ルーク $1$ を取り、右下方向に進み続けてルーク $4$ を取る - です。ここでの手数は $7$ 手であり、これが出力例の三つ目の数です。

path

$x$ 軸正方向: 右、 $y$ 軸正方向: 上

ルーク $2, 5, 6$ のいずれかをキングに置き換えた場合には、他のルークを一個も取ることができません。このとき、最小手数は $0$ です。

入力例 2Copy

Copy

出力例 2Copy

Copy

入力例 3Copy

Copy

出力例 3Copy

Copy

Score : $2200$ points

Problem Statement

You are given positions $(X_i, Y_i)$ of $N$ enemy rooks on an infinite chessboard. No two rooks attack each other (at most one rook per row or column).

You're going to replace one rook with a king and then move the king repeatedly to beat as many rooks as possible.

You can't enter a cell that is being attacked by a rook. Additionally, you can't move diagonally to an empty cell (but you can beat a rook diagonally).

(So this king moves like a superpawn that beats diagonally in 4 directions and moves horizontally/vertically in 4 directions.)

For each rook, consider replacing it with a king, and find the minimum possible number of moves needed to beat the maximum possible number of rooks.

Constraints

$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$
All values in input are integers.

Input

Input is given from Standard Input in the following format.

 $N$ 
 $X_1$   $Y_1$ 
 $X_2$   $Y_2$ 
 $\vdots$ 
 $X_N$   $Y_N$

Output

Print $N$ lines. The $i$ -th line is for scenario of replacing the rook at $(X_i, Y_i)$ with your king. This line should contain one integer: the minimum number of moves to beat $M_i$ rooks where $M_i$ denotes the maximum possible number of beaten rooks in this scenario (in infinite time).

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

See the drawing below. If we replace rook 3 with a king, we can beat at most two other rooks. The red path is one of optimal sequences of moves: beat rook 1, then keep going down and right until you can beat rook 4. There are 7 steps and that's the third number in the output.

path

x-coordinate increases from left to right, while y increases bottom to top.

Starting from rook 2, 5 or 6, we can't beat any other rook. The optimal number of moves is 0.

Sample Input 2Copy

Copy

Sample Output 2Copy

Copy

Sample Input 3Copy

Copy

Sample Output 3Copy

Copy