Ночная операция

Несмотря на странные ограничения, на самом деле в этой задаче $$$\text{int}128$$$ не требуется.

Запишем уравнение координаты от времени для детективов и для зевак:

Сначала запишем для зевак, до которых луч достает сразу: $$$$$$ \begin{cases} x_1(t) = t \\ x_2(t) = b_i - \dfrac{at^2}{2} \end{cases} $$$$$$ $$$$$$x_1(t) = x_2(t) $$$$$$

$$$$$$\dfrac{at^2}{2} + t - b_i = 0$$$$$$ $$$$$$ t_{1,2} = \dfrac{-1 \pm \sqrt{1 + 2ab_i}}{a}$$$$$$

Так как отрицательное время нам не подходит, $$$t = \dfrac{-1 + \sqrt{1 + 2ab_i}}{a}$$$, тогда скорость в момент времени $$$t$$$ равна $$$at$$$, то есть $$$-1 + \sqrt{1 + 2ab_i}$$$. Теперь разберемся, что такое $$$(V+1)^2$$$, это $$$1 + 2ab_i$$$.

Для второго случая аналогично $$$(V+1)^2 = 1 + 2aH$$$. $$$$$$\left(\begin{cases} x_1(t) = b_i - H + t \\ x_2(t) = b_i - \dfrac{at^2}{2}\end{cases}\right) $$$$$$

Таким образом, нам нужно найти $$$H$$$, что

$$$$$$\sum^{n}_{i=1} \begin{cases} 1 + 2ab_i & H \le b_i \\ 1 + 2aH & H \gt b_i \end{cases} $$$$$$

Эта функция монотонно возрастает относительно $$$i$$$, значит в этой задаче можно применить бинарный поиск. Так как в задаче гарантируется, что ответ существует, значит, что при $$$H = \max(b_i)$$$, ответ должен быть «0», а если подставить $$$H=1$$$, то сумма получится $$$2an + n$$$, что не больше чем $$$3an$$$.

Так как $$$b_i \cdot n \le 10^{18}$$$, в какой-то момент сумма может стать больше $$$M$$$, но она будет помещаться в $$$\text{long long}$$$.

Асимптотика решения: $$$\mathcal{O}(n\log n)$$$