#PU1349. USACO 2023 December Contest, Bronze — Problem 3. Farmer John Actually Farms

USACO 2023 December Contest, Bronze — Problem 3. Farmer John Actually Farms

USACO 2023 December Contest, Bronze — Problem 3. Farmer John Actually Farms

题目描述

Farmer John is growing NN (1≤N≤2⋅1051 \leq N \leq 2\cdot 10^5) plants of asparagus on his farm! However some of his plants have genetic differences, so some plants will grow faster than others. The initial height of the iith plant is hih_i inches, and after each day, the iith plant grows by aia_i inches. FJ likes some of his plants more than others, and he wants some specific plants to be taller than others. He gives you an array of distinct values t1,…,tNt_1,\dots,t_N containing all integers from 00 to N−1N-1 and he wants the iith plant to have exactly tit_i other plants that are taller than it. Find the minimum number of days so that FJ's request is satisfied, or determine that it is impossible.

输入格式

The first will consist of an integer TT, denoting the number of independent test cases (1≤T≤10)(1 \leq T \leq 10). The first line of each test case consists of an integer NN. The second line consists of NN integers hih_i (1≤hi≤109)(1 \leq h_i \leq 10^9) denoting the initial height of the iith plant in inches. The third line consists of NN integers aia_i (1≤ai≤109)(1 \leq a_i \leq 10^9) denoting the number of inches the iith plant grows each day. The fourth line consists of NN distinct integers tit_i denoting the array that FJ gives you. It is guaranteed that the sum of NN over all test cases does not exceed 2⋅1052\cdot 10^5.

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

6
1
10
1
0
2
7 3
8 10
1 0
2
3 6
10 8
0 1
2
7 3
8 9
1 0
2
7 7
8 8
0 1
2
7 3
8 8
1 0
0
3
2
5
-1
-1
In the first sample input, there are 6 test cases.
In the first test case, there is only one plant, so the condition is satisfied
on day 0.
In the second test case, we need the first plant to be shorter than the second
plant.  After day 1, the heights are 15 and 13.  After day 2, the heights are
both 23.  After day 3, the heights are 31 and 33, and that's the first day in
which the condition is satisfied.
The third and fourth test cases are similar to the second.
In the fifth test case, both plants start with an initial height of 7 and a
growth rate of 8.  So they will always have identical heights, and therefore the
condition is never satisfied.
In the sixth test case, the condition is not satisfied initially and the growth
rates are the same. So the condition can never be satisfied.

样例 2

2
5
7 4 1 10 12
3 4 5 2 1
2 1 0 3 4
5
4 10 12 7 1
3 1 1 4 5
2 4 3 1 0
4
7
In the second sample input, there are 2 test cases.
In the first test case, the final heights after day 4 are 19, 20, 21, 18, 16.
In the second test case, the final heights after day 7 are 25, 17, 19, 35, 36.

提示

use of 64-bit integer data types (e.g., a "long long" in C/C++).