7427. 线段轨迹 II (Line Segments Trace II)
时间限制：1000 MS 内存限制：512 MB
题目描述
# 线段轨迹 II (Line Segments Trace II) 时间限制：$1.00\text{ s}$ 空间限制：$512\text{ MB}$ ## 题目描述 有 $n$ 条线段，其端点坐标均为整数。所有端点的横坐标范围在 $0$ 到 $m$ 之间。每条线段的斜率均为整数。 对于每一个横坐标 $x = 0, 1, \dots, m$，求出覆盖此位置的所有线段中的最大 $y$ 坐标。如果在某个 $x$ 位置没有任何线段覆盖，则该位置的最大坐标记为 $-1$。 ## 输入格式 第一行包含两个整数 $n$ 和 $m$：线段的数量以及最大横坐标。 接下来的 $n$ 行描述这些线段。每行包含四个整数 $x_1, y_1, x_2$ 和 $y_2$，表示在点 $(x_1, y_1)$ 与 $(x_2, y_2)$ 之间有一条线段。 ## 输出格式 输出 $m + 1$ 个整数：分别对应 $x = 0, 1, \dots, m$ 处的最大 $y$ 坐标（如无覆盖则输出 $-1$）。 ## 输入输出样例 ### 输入 #1 ```text 4 5 1 1 3 3 1 2 4 2 2 4 5 7 2 8 5 2 ``` ### 输出 #1 ```text -1 2 8 6 6 7 ``` ## 说明/提示 ### 数据规模与约定 - $1 \le n, m \le 10^5$ - $0 \le x_1 < x_2 \le m$ - $0 \le y_1, y_2 \le 10^9$