問題一覧 > 通常問題

No.2743 Twisted Lattice

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 31
作問者 : Nzt3Nzt3 / テスター : tassei903tassei903 kenken714kenken714 ponjuiceponjuice cho435cho435
1 ProblemId : 10835 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-04-19 15:21:07

問題文

縦 $H$ マス、横 $W$ マスのマス目があります。

上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ と表記します。

  • $1\le i < H,1 \le j \le W$ において、 $(i,j)$ と $(i+1,j)$ は時間 $1$ で相互に行き来可能です。
  • $1\le i \le H,1 \le j < W$ において、 $(i,j)$ と $(i,j+1)$ は時間 $i$ で相互に行き来可能です。

マス目上には $N$ 個の出口があり、出口 $i$ は $(A_i,B_i)$ にあります。

$x=1,2,\ldots ,N$について次の問題を解いてください。

  • 始め出口 $x$ にいます。別の出口までの移動にかかる時間のうち、最小のものを求めてください。

制約

  • $1 \le H \le 10^9$
  • $1 \le W \le 10^9$
  • $2 \le H\times W$
  • $2 \le N \le 2 \times 10^5$
  • $1 \le A_i \le H$
  • $1 \le B_i \le W$
  • $i\not=j$ のとき $(A_i,B_i)\not=(A_j,B_j)$
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$H$ $W$ $N$
$A_1$ $B_1$
$\vdots$
$A_N$ $B_N$

出力

$N$ 行出力せよ。 $i$ 行目には $x=i$ のときの問題の答えを出力せよ。

サンプル

サンプル1
入力
10 10 6
1 2
2 3
3 3
10 7
8 2
3 5
出力
2
1
1
13
7
5

出力の $1$ 行目について、出口 $2$ への移動にかかる最短時間が $2$ であり、これが最小です。

出力の $2$ 行目について、出口 $3$ への移動にかかる最短時間が $1$ であり、これが最小です。

サンプル2
入力
1000000000 1000000000 2
1000000000 1
1000000000 1000000000
出力
2999999997
2999999997

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。