CF1706D2 Chopping Carrots (Hard Version)

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$.

N/A

N/A

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] $ .