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