Roadwork

题目描述

有一条无限长的街道自西向东延伸，我们把它看作一条数轴。 这条街上安排了 $N$ 个道路施工。 第 $i$ 个施工在坐标为 $X_i$ 的点从时间 $S_i - 0.5$ 到时间 $T_i - 0.5$ 被封闭。 $Q$ 个人站在坐标 $0$。第 $i$ 个人将在时间 $D_i$ 从坐标 $0$ 出发，以速度 $1$ 向正方向行走，遇到被封闭的点时停止行走。 求每个 $Q$ 个人将行走的距离。

输入格式

输入按下述格式由标准输入提供： $N$ $Q$ $S_1$ $T_1$ $X_1$ : $S_N$ $T_N$ $X_N$ $D_1$ : $D_Q$

输出格式

输出 $Q$ 行。第 $i$ 行应当包含第 $i$ 个人将行走的距离，若该人会无止境行走则输出 $-1$。

4 6
1 3 2
7 13 10
18 20 13
3 4 2
0
1
2
3
5
8

2
2
10
-1
13
-1

提示

输入中的所有数值都是整数。 $1 \leq N, Q \leq 2 \times 10^5$ 0 \leq S_i < T_i \leq 10^9 $1 \leq X_i \leq 10^9$ 0 \leq D_1 < D_2 < ... < D_Q \leq 10^9 如果 $i \neq j$ 且 $X_i = X_j$，则区间 $[S_i, T_i)$ 和 $[S_j, T_j)$ 不重叠。第一个人在时间 $0$ 从坐标 $0$ 出发，并在到达坐标 $2$ 时被第一个在时间 $2$ 封闭的施工点阻止而停止行走。 第二个人在时间 $1$ 从坐标 $0$ 出发，在时间 $3$ 到达坐标 $2$。第一个施工已经结束，但第四个施工已经开始，因此该人也在坐标 $2$ 停下。 第四和第六个人在行走过程中没有遇到任何施工，因此他们会无止境行走。这些情况的输出为 $-1$。

标签: AtCoder|abc128E

来源

AtCoder|abc128E