Falling Portals

题目描述

有 $N$ 个（$2\le N\le 2\cdot 10^5$）世界，每个世界都有一个传送门。初始时，世界 $i$（$1 \leq i \leq N$）的 $x$ 坐标为 $i$，$y$ 坐标为 $A_i$（$1\le A_i\le 10^9$）。每个世界上还有一头牛。在时间 $0$ 时，所有 $y$ 坐标互不相同，随后世界开始下落：世界 $i$ 以每秒 $i$ 个单位的速度沿负 $y$ 方向连续移动。 在任意时刻，只要两个世界处在相同的 $y$ 坐标（时间可能为分数），它们的传送门就会“对齐”，这意味着位于其中一个世界上的牛可以选择瞬间传送到另一个世界。 对每个 $i$，世界 $i$ 上的牛想要前往世界 $Q_i$（$Q_i\neq i$）。请帮助每头牛确定：如果她以最优方式旅行，她的旅程将花费多长时间。 每个询问的输出应为一个分数 $a/b$，其中 $a$ 与 $b$ 为正且互质的整数；如果旅程不可能，则输出 $-1$。

输入格式

输入格式（文件 falling.in）： 输入第一行包含一个整数 $N$。 第二行包含 $N$ 个用空格分隔的整数 $A_1,A_2,\ldots,A_N$。 第三行包含 $N$ 个用空格分隔的整数 $Q_1,Q_2,\ldots,Q_N$。

输出格式

输出格式（文件 falling.out）： 输出 $N$ 行，第 $i$ 行包含第 $i$ 头牛的旅程时长。

4
3 5 10 2
3 3 2 1

7/2
7/2
5/1
-1

提示

评分（SCORING）： 测试点 2-3 满足 $N\le 100$。 测试点 4-5 满足 $N\le 2000$。 测试点 6-14 无额外限制。

考虑最初在世界 2 上的牛的答案。在时间 $2$ 时，世界 1 和 2 对齐，因此牛可以传送到世界 1。在时间 $\frac{7}{2}$ 时，世界 1 和 3 对齐，因此牛可以传送到世界 3。 题目出题人：Dhruv Rohatgi

标签: USACO|2020|Platinum

来源

USACO|2020|Platinum