P6010 [USACO20JAN] Falling Portals P

There are $N$ worlds ($2 \leq N \leq 2 \times 10^5$), and each world has a portal. Initially, world $i$ (for $1 \leq i \leq N$) is at $x$-coordinate $i$ and $y$-coordinate $A_i$ ($1 \leq A_i \leq 10^9$). Each world also contains a cow. At time $0$, all $y$-coordinates are distinct, and then the worlds begin to fall: world $i$ moves along the negative $y$-axis at a speed of $i$ units per second. At any time, if two worlds have the same $y$-coordinate at some moment (possibly at a non-integer time), their portals will “synchronize”, allowing a cow in one world to choose to instantly teleport to the other world. For each $i$, the cow in world $i$ wants to go to world $Q_i$ ($Q_i \neq i$). Help each cow compute how much time it takes if she moves in the best possible way. Each query should be output as a fraction $a/b$, where $a$ and $b$ are coprime positive integers, or $-1$ if it is impossible to reach.

The first line contains an integer $N$. The next line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$. The next line contains $N$ space-separated integers $Q_1, Q_2, \ldots, Q_N$.

Output $N$ lines. The $i$-th line contains the travel time for cow $i$.

### Sample Explanation Consider the answer for the cow originally in world $2$. At time $2$, worlds $1$ and $2$ synchronize, so the cow can go to world $1$. At time $\frac{7}{2}$, worlds $1$ and $3$ synchronize, so the cow can go to world $3$. ### Subtasks - Test points $2 \sim 3$ satisfy $N \leq 100$. - Test points $4 \sim 5$ satisfy $N \leq 2000$. - Test points $6 \sim 14$ have no additional constraints. Translated by ChatGPT 5