Codeforces Round 809 (Div. 2) |
---|
Finished |
This is the hard version of the problem. The only difference between the versions is the constraints on $$$n$$$, $$$k$$$, $$$a_i$$$, and the sum of $$$n$$$ over all test cases. You can make hacks only if both versions of the problem are solved.
Note the unusual memory limit.
You are given an array of integers $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$, and an integer $$$k$$$.
The cost of an array of integers $$$p_1, p_2, \ldots, p_n$$$ of length $$$n$$$ is $$$$$$\max\limits_{1 \le i \le n}\left(\left \lfloor \frac{a_i}{p_i} \right \rfloor \right) - \min\limits_{1 \le i \le n}\left(\left \lfloor \frac{a_i}{p_i} \right \rfloor \right).$$$$$$
Here, $$$\lfloor \frac{x}{y} \rfloor$$$ denotes the integer part of the division of $$$x$$$ by $$$y$$$. Find the minimum cost of an array $$$p$$$ such that $$$1 \le p_i \le k$$$ for all $$$1 \le i \le n$$$.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.
The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 10^5$$$).
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_1 \le a_2 \le \ldots \le a_n \le 10^5$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.
For each test case, print a single integer — the minimum possible cost of an array $$$p$$$ satisfying the condition above.
75 24 5 6 8 115 124 5 6 8 113 12 9 157 32 3 5 5 6 9 106 5654 286 527 1436 2450 26813 9516 340 22412 21 3
2 0 13 1 4 7 0
In the first test case, the optimal array is $$$p = [1, 1, 1, 2, 2]$$$. The resulting array of values of $$$\lfloor \frac{a_i}{p_i} \rfloor$$$ is $$$[4, 5, 6, 4, 5]$$$. The cost of $$$p$$$ is $$$\max\limits_{1 \le i \le n}(\lfloor \frac{a_i}{p_i} \rfloor) - \min\limits_{1 \le i \le n}(\lfloor \frac{a_i}{p_i} \rfloor) = 6 - 4 = 2$$$. We can show that there is no array (satisfying the condition from the statement) with a smaller cost.
In the second test case, one of the optimal arrays is $$$p = [12, 12, 12, 12, 12]$$$, which results in all $$$\lfloor \frac{a_i}{p_i} \rfloor$$$ being $$$0$$$.
In the third test case, the only possible array is $$$p = [1, 1, 1]$$$.
Name |
---|