Last Man Standing
Contest: Educational Codeforces Round 155 (Rated for Div. 2)
Difficulty rating: 2800
Tags: brute force, data structures, number theory

There are $$$n$$$ heroes in a videogame. Each hero has some health value $$$h$$$ and initial armor value $$$a$$$. Let the current value of armor be $$$a_{\mathit{cur}}$$$, initially equal to $$$a$$$.

When $$$x$$$ points of damage are inflicted on a hero, the following happens: if $$$x < a_{\mathit{cur}}$$$, then $$$x$$$ gets subtracted from $$$a_{\mathit{cur}}$$$; otherwise, $$$1$$$ gets subtracted from $$$h$$$ and $$$a_{\mathit{cur}}$$$ gets assigned back to $$$a$$$.

In the start of the game, you choose the value $$$x$$$ (an integer strictly greater than $$$0$$$, arbitrarily large). Then you keep attacking all heroes in rounds: in one round, you inflict $$$x$$$ points of damage to all alive heroes. A hero dies when his health becomes $$$0$$$. The game ends when all heroes are dead.

The last hero to die earns the number of points, equal to the number of rounds he was the only hero alive. The other heroes get $$$0$$$ points. In particular, if the last round ends with multiple heroes dying, then every hero gets $$$0$$$ points.

The game is played for every possible $$$x$$$ (from $$$1$$$ to infinity). The points are reset between the games. What's the maximum number of points each hero has had?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10$$$) — the number of testcases.

The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of heroes.

The second line contains $$$n$$$ integers $$$h_1, h_2, \dots, h_n$$$ ($$$1 \le h_i \le 2 \cdot 10^5$$$) — the health value of each hero.

The third line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — the initial armor value of each hero.

Output format:
For each testcase, print $$$n$$$ integers — the maximum number of points each hero has had over the games played for every possible $$$x$$$.

Constraints:
Time limit: 7.0 s
Memory limit: 512.0 MB

Note:
In the first testcase, the game for $$$x = 1$$$ is played as follows:

- before all rounds: the heroes have $$$h = [3, 1, 2]$$$, $$$a_{\mathit{cur}} = [3, 11, 5]$$$;
- round $$$1$$$: $$$1$$$ damage is inflicted on every hero: $$$h$$$ remains $$$[3, 1, 2]$$$, $$$a_{\mathit{cur}}$$$ becomes $$$[2, 10, 4]$$$;
- round $$$2$$$: $$$h = [3, 1, 2]$$$, $$$a_{\mathit{cur}} = [1, 9, 3]$$$;
- round $$$3$$$: the first hero runs out of armor, so he loses a health point: $$$h = [2, 1, 2]$$$, $$$a_{\mathit{cur}} = [3, 8, 2]$$$;
- ...
- round $$$9$$$: the first hero dies, since his health reaches $$$0$$$: $$$h = [0, 1, 1]$$$, $$$a_{\mathit{cur}} = [0, 2, 1]$$$;
- round $$$10$$$: the third hero dies: $$$h = [0, 1, 0]$$$, $$$a_{\mathit{cur}} = [0, 1, 0]$$$;
- round $$$11$$$: the second hero dies: $$$h = [0, 0, 0]$$$, $$$a_{\mathit{cur}} = [0, 0, 0]$$$.

The second hero was the last hero to die, and he was the only hero alive during one round. Thus, he gets $$$1$$$ point for that game.

The game for $$$x = 4$$$ is played as follows:

- round $$$1$$$: $$$h = [2, 1, 2]$$$, $$$a_{\mathit{cur}} = [3, 7, 1]$$$;
- round $$$2$$$: $$$h = [1, 1, 1]$$$, $$$a_{\mathit{cur}} = [3, 3, 5]$$$;
- round $$$3$$$: $$$h = [0, 0, 1]$$$, $$$a_{\mathit{cur}} = [0, 0, 1]$$$;
- round $$$4$$$: $$$h = [0, 0, 0]$$$, $$$a_{\mathit{cur}} = [0, 0, 0]$$$;

The third hero was the last hero to die, and he was the only hero alive during one round.

Example input:
3
3
3 1 2
3 11 5
1
100
200
4
5 9 5 1
9 2 9 10

Example output:
1 1 1 
20000 
0 4 0 0

Editorial:
For each $$$x$$$, we can easily tell how many rounds each hero will last. That is equal to $$$\lceil \frac{a}{x} \rceil \cdot h$$$. The last hero to die is the one with the maximum of this value. And the number of rounds he will be the only hero alive is determined by the second maximum.
Also notice that all $$$x$$$ that are greater or equal to the maximum of $$$a$$$ behave the same. In one round, all heroes just lose one point of health. Thus, it only makes sense to calculate the answer for all $$$x$$$ from $$$1$$$ to $$$\max{a}$$$.
The problem currently is the following: for each $$$x$$$ from $$$1$$$ to $$$\max{a}$$$, find the index and the value of the maximum and the value of the second maximum of $$$\lceil \frac{a}{x} \rceil \cdot h$$$.
Let's group all heroes by the value of $$$c = \lceil \frac{a}{x} \rceil$$$. The values of $$$a$$$ for the heroes in the group form a segment from $$$x \cdot (c - 1) + 1$$$ to $$$x \cdot c$$$. From each group, we only care about the maximum and the second maximum over $$$h$$$. Thus, if we can extract the maximum and the second maximum in $$$O(1)$$$, the solution will be $$$O(a \log a)$$$ because of the harmonic series (iterating over $$$x$$$, then over $$$\lceil \frac{a}{x} \rceil$$$).
First, for each $$$a$$$, find the maximum and the second maximum of $$$h$$$. To query the maximum on a segment, we can use a sparse table. Apparently, we can modify it to query the second maximum as well.
Store a tuple of (value of maximum, index of maximum, value of the second maximum). To merge two segments, we compare if the indices of the maximums are the same. They can possibly be the same because we often query intersecting segments in the sparse table. If they are, the second maximum is the largest of the respective second maximums. If they aren't, let the first node has a large or equal value of maximum. Then the second maximum is the larger of the second maximum of the first node and the maximum of the second node.
Overall complexity: $$$O(n + a \log a)$$$ time and memory per testcase.