AT_abc128_e [ABC128E] Roadwork

题目描述

有一条东西方向无限延伸的大道，可以看作是一条数轴。

在这条大道上将进行 $N$ 次道路施工。第 $i$ 次道路施工会在时刻 $S_i - 0.5$ 到时刻 $T_i - 0.5$ 期间，使坐标 $X_i$ 处禁止通行。

有 $Q$ 个人站在坐标 $0$ 处。第 $i$ 个人会在时刻 $D_i$ 从坐标 $0$ 出发，以速度 $1$ 向正方向一直行走。如果在行走过程中到达了正在禁止通行的坐标，则会在该处停止行走。

请计算每个人能够前进的距离。如果某个人可以无限行走下去，则输出 $-1$。

输入格式

输入通过标准输入按以下格式给出。

$N$ $Q$
$S_1$ $T_1$ $X_1$
$\vdots$
$S_N$ $T_N$ $X_N$
$D_1$
$\vdots$
$D_Q$

输出格式

输出共 $Q$ 行。

第 $i$ 行输出第 $i$ 个人能够前进的距离。如果第 $i$ 个人可以无限行走，则输出 $-1$。

样例 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 < \cdots < D_Q \leq 10^9$
• 若 $i \neq j$ 且 $X_i = X_j$，则区间 $[S_i, T_i)$ 与区间 $[S_j, T_j)$ 不重叠。

样例解释 1

第 $1$ 个人在时刻 $0$ 从坐标 $0$ 出发，在时刻 $2$ 到达坐标 $2$ 时，由于第 $1$ 次道路施工导致该处禁止通行，因此停止行走。第 $2$ 个人在时刻 $1$ 从坐标 $0$ 出发，在时刻 $3$ 到达坐标 $2$。此时第 $1$ 次道路施工已结束，但第 $4$ 次道路施工已经开始，因此同样在坐标 $2$ 停止行走。第 $4$ 个人和第 $6$ 个人在行走过程中不会遇到任何禁止通行的点，因此可以无限行走。

由 ChatGPT 4.1 翻译