3340. [USACO20 Jan Platinum]Falling Portals

【题目描述】

有 $N(2\le N\le 2 ×10^5)$个世界，每个世界有一个传送门。初始时，世界 $i$(对于 $1 \leq i \leq N$)位于 $x$ 坐标 $i$，$y$ 坐标 $A_i (1\le A_i\le 10^9)$。每个世界里还有一头奶牛。在时刻 $0$，所有的 $y$ 坐标各不相同，然后这些世界开始坠落：世界 $i$ 沿着 $y$ 轴负方向以 $i$ 单位每秒的速度移动。

在任意时刻，如果两个世界在某一时刻 $y$ 坐标相同(可能是非整数时刻)，传送门之间就会“同步”，使得其中一个世界的奶牛可以选择瞬间传送到另一个世界。

对于每一个 $i$，在世界 $i$ 的奶牛想要去往世界 $Q_i(Q_i\neq i)$。帮助每头奶牛求出如果她以最优方案移动需要多少时间。

每个询问的输出是一个分数$\frac{a}{b}$，其中 $a$ 和 $b$ 为互质的正整数，如果不可能到达,则输出 $-1$。

【输入格式】

输入的第一行包含一个整数 $N$。

下一行包含 $N$ 个空格分隔的整数 $A_1,A_2,\ldots,A_N$。

下一行包含 $N$ 个空格分隔的整数 $Q_1,Q_2,\ldots,Q_N$。

【输出格式】

输出 $N$ 行，第 $i$ 行包含奶牛 $i$ 的旅程的时间。

【样例输入】

4
3 5 10 2
3 3 2 1

【样例输出】

7/2
7/2
5/1
-1

【样例解释】

考虑原先在世界 2 的奶牛的答案。在时刻 $2$ 世界 1 和世界 2 同步，所以奶牛可以前往世界 1。在时刻 $\frac{7}{2}$ 世界 1 和世界 3 同步，所以奶牛可以前往世界 3。

【提示】

对于$ 22\% $的测试数据(测试点$ 1\sim3 $)，满足$ N ≤ 100 $。

另有$ 15\% $的测试数据(测试点$ 4\sim5 $)，满足$ N ≤ 2,000 $。

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。

【来源】

USACO 一月公开赛 Platinum 组