分数: 600 点
问题陈述
有一个正方形网格, H+1 水平行和 W 垂直列。
您将从顶行的一个方格开始,然后重复向右或向下移动一个方格。然而,对于每个整数 i 来自 1 通过 H,您无法从 A_i-th, (A_i + 1)-th, \ldots, B_i从左边开始第一个方格 i从顶部算起的第 3 行。
对于每个整数 k 来自 1 通过 H,找到到达其中一个方格所需的最小移动次数 (k+1)从顶部算起的第 3 行。 (可以针对每种情况单独选择起始方格。)如果从顶行中的任何方格开始, (k+1)可以到达第行,打印 -1 。
约束
- 1 \leq H,W \leq 2\times 10^5
- 1 \leq A_i \leq B_i \leq W
输入
输入由标准输入按以下格式给出:
H W A_1 B_1 A_2 B_2 : A_H B_H
输出
打印 H 行。的 i- 第行应包含案例的答案 k=i.
示例输入 1
4 4 2 4 1 1 2 3 2 4
示例输出 1
1 3 6 -1
让 (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,不可能到达从上往下数第五行的任何方格。