Falling Portals

提交数: 2, 通过率: 50%, 平均分: 67.5

题目描述:

有 N（2≤N≤2⋅105）个世界，每个世界有一个传送门。初始时，世界 i（对于 1≤i≤N）位于 x 坐标 i，y 坐标 Ai（1≤Ai≤109）。每个世界里还有一头奶牛。在时刻 0，所有的 y 坐标各不相同，然后这些世界开始坠落：世界 i 沿着 y 轴负方向以 i 单位每秒的速度移动。

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

对于每一个 i，在世界 i 的奶牛想要去往世界 Qi（Qi≠i）。帮助每头奶牛求出如果她以最优方案移动需要多少时间。

每个询问的输出是一个分数 a/b，其中 a 和 b 为互质的正整数，或者 −1，如果不可能到达。

测试点性质：
  • 测试点 2-3 满足N≤100。
  • 测试点 4-5 满足 N≤2000。
  • 测试点 6-14 没有额外限制。

输入格式:

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

下一行包含 N 个空格分隔的整数 A1,A2,…,AN。

下一行包含 N 个空格分隔的整数 Q1,Q2,…,QN。

输出格式:

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

样例输入:

4
3 5 10 2
3 3 2 1

样例输出:

7/2
7/2
5/1
-1

提示:

考虑原先在世界 2 的奶牛的答案。在时刻 2 世界 1 和世界 2 同步，所以奶牛可以前往世界 1。在时刻 72 世界 1 和世界 3 同步，所以奶牛可以前往世界 3。

时间限制: 1000ms
空间限制: 256MB

来源: USACO 2020 JAN Platinum