I hate Shortest Path Problem

题目描述

有一个由方格组成的网格，具有 $H+1$ 条水平行和 $W$ 列垂直列。 你将从顶行的某一格开始，重复向右或向下移动一格。然而，对于每个整数 $i$（从 $1$ 到 $H$），你不能从从上数第 $i$ 行中从左数第 $A_i$ 个、第 $(A_i + 1)$ 个、…、第 $B_i$ 个格子向下移动。 对于每个整数 $k$（从 $1$ 到 $H$），找出到达从上数第 $k+1$ 行的某一格所需的最小移动次数。（起始格子可以为每一种情况单独选择。）如果从顶行的任一格出发，都无法到达从上数第 $k+1$ 行的任何格子，则输出 $-1$。

输入格式

输入按下述格式由标准输入给出： $H$ $W$ $A_1$ $B_1$ $A_2$ $B_2$ : $A_H$ $B_H$

输出格式

输出 $H$ 行。第 $i$ 行应包含 $k=i$ 的情况的答案。

4 4
2 4
1 1
2 3
2 4

1
3
6
-1

提示

$1 \leq H,W \leq 2\times 10^5$ $1 \leq A_i \leq B_i \leq W$记 $(i,j)$ 表示从上数第 $i$ 行、第 $j$ 列的格子。 对于 $k=1$，我们需要一次移动，例如 $(1,1)$ → $(2,1)$。 对于 $k=2$，我们需要三次移动，例如 $(1,1)$ → $(2,1)$ → $(2,2)$ → $(3,2)$。 对于 $k=3$，我们需要六次移动，例如 $(1,1)$ → $(2,1)$ → $(2,2)$ → $(3,2)$ → $(3,3)$ → $(3,4)$ → $(4,4)$。 对于 $k=4$，从顶数第五行的任何格子都无法到达。

标签: AtCoder|abc177F

来源

AtCoder|abc177F