[USACO20JAN] Falling Portals P
题目描述
有 $N$($2 \leq N \leq 2 \times 10^5$)个世界,每个世界有一个传送门。初始时,世界 $i$(对于 $1 \leq i \leq N$)位于 $x$ 坐标 $i$,$y$ 坐标 $A_i$($1 \leq A_i \leq 10^9$)。每个世界里还有一头奶牛。在时刻 $0$,所有的 $y$ 坐标各不相同,然后这些世界开始坠落:世界 $i$ 沿着 $y$ 轴负方向以 $i$ 单位每秒的速度移动。
在任意时刻,如果两个世界在某一时刻 $y$ 坐标相同(可能是非整数时刻),传送门之间就会“同步”,使得其中一个世界的奶牛可以选择瞬间传送到另一个世界。
对于每一个 $i$,在世界 $i$ 的奶牛想要去往世界 $Q_i$($Q_i \neq i$)。帮助每头奶牛求出如果她以最优方案移动需要多少时间。
每个询问的输出是一个分数 $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$ 的旅程的时间。
输入输出样例
输入样例 #1
4
3 5 10 2
3 3 2 1
输出样例 #1
7/2
7/2
5/1
-1
说明
### 样例解释
考虑原先在世界 $2$ 的奶牛的答案。在时刻 $2$ 世界 $1$ 和世界 $2$ 同步,所以奶牛可以前往世界 $1$。在时刻 $\frac{7}{2}$ 世界 $1$ 和世界 $3$ 同步,所以奶牛可以前往世界 $3$。
### 子任务
- 测试点 $2 \sim 3$ 满足 $N \leq 100$。
- 测试点 $4 \sim 5$ 满足 $N \leq 2000$。
- 测试点 $6 \sim 14$ 没有额外限制。