#PU998. USACO 2020 January Contest, Platinum — Problem 3. Falling Portals

    ID: 1536 传统题 文件IO:falling 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:jan20来源:usaco.orgscoring:equal_test_cases

USACO 2020 January Contest, Platinum — Problem 3. Falling Portals

USACO 2020 January Contest, Platinum — Problem 3. Falling Portals

题目描述

There are NN (2≤N≤2⋅1052\le N\le 2\cdot 10^5) worlds, each with a portal. Initially, world ii (for 1≤i≤N1 \leq i \leq N) is at xx-coordinate ii, and yy-coordinate AiA_i (1≤Ai≤1091\le A_i\le 10^9). There is also a cow on each world. At time 00, all yy-coordinates are distinct and the worlds start falling: world ii moves continuously in the negative-yy direction at a speed of ii units per second. At any time when two worlds are at the same yy-coordinate (possibly a fractional time), the portals "align", meaning that a cow on one of the worlds can choose to travel instantaneously to the other world. For each ii, the cow on world ii wants to travel to world QiQ_i (Qi≠iQ_i\neq i). Help each cow determine how long her journey will take, if she travels optimally. Each query output should be a fraction a/ba/b where aa and bb are positive and relatively prime integers, or −1-1 if it the journey is impossible.

输入格式

The first line of input contains a single integer N.N. The next line contains NN space-separated integers A1,A2,…,AN.A_1,A_2,\ldots,A_N. The next line contains NN space-separated integers Q1,Q2,…,QN.Q_1,Q_2,\ldots,Q_N.

输出格式

Print NN lines, the ii-th of which contains the journey length for cow i.i.

数据范围

Test cases 2-3 satisfy N≤100.N\le 100. Test cases 4-5 satisfy N≤2000.N\le 2000. Test cases 6-14 satisfy no additional constraints.

样例

样例 1

4
3 5 10 2
3 3 2 1
7/2
7/2
5/1
-1
Consider the answer for the cow originally on world 2. At time $2$ worlds 1 and
2 align, so the cow can travel to world 1. At time $\frac{7}{2}$ worlds 1 and 3
align, so the cow can  travel to world 3.
Problem credits: Dhruv Rohatgi