Задача №115130. Шлюзы
Участникам, использующим язык Python3 , рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3 .
Недавно в Диваново построили огромную шлюзовую систему. Всего было построено \(n\) шлюзов, \(i\)-й из них имеет объем \(v_i\) литров. Изначально все шлюзы пусты. В каждый шлюз ведет труба, при открытии которой в шлюз будет поступать по \(1\) литру воды в секунду. Исходно все трубы закрыты.
Шлюзовая система устроена так, что если доливать воду в \(i\)-й шлюз сверх его объема, она будет моментально моментально переливаться в шлюз с номером \(i + 1\). Если шлюз c номером \(i + 1\) тоже заполнен, вода будет переливаться дальше. Вода из последнего шлюза будет выливаться в озеро.
Рисунок показывает \(5\) шлюзов с открытыми трубами к шлюзам \(1\) и \(3\). Так как шлюзы \(1\), \(3\) и \(4\) уже заполнены, фактически вода идет в шлюзы \(2\) и \(5\).
Для того, чтобы шлюзы начали функционировать, необходимо заполнить каждый из них. Мэра Дивановской области интересует \(q\) независимых запросов. Для каждого запроса предположим, что изначально все шлюзы пусты и все трубы закрыты, затем одновременно открываются несколько труб. Для \(j\)-го запроса мэр хочет знать, какое минимальное число труб надо включить, чтобы не позже чем через \(t_j\) секунд все шлюзы стали заполнены.
Помогите мэру справиться с этой сложной задачей и ответьте на все его запросы!
В первой строке вводится одно целое число \(n\) (\(1 \le n \le 200\,000\)) — количество шлюзов.
Во второй строке вводятся \(n\) целых чисел \(v_1, v_2, \dots, v_n\) (\(1 \le v_i \le 10^9\)) — объемы шлюзов.
В третьей строке вводится одно целое число \(q\) (\(1 \le q \le 200\,000\)) — число запросов.
В следующих \(q\) строках вводится по одному целому числу \(t_i\) (\(1 \le t_j \le 10^9\)) — время, за которое нужно наполнить все шлюзы в \(j\)-м запросе.
Выведите \(q\) чисел, \(j\)-е из них должно быть равно минимальному числу труб, которое нужно открыть, чтобы наполнить все шлюзы за время \(t_j\). Если за это время наполнить всю шлюзы невозможно, выведите \(-1\).
В первом примере \(6\) запросов:
В запросах \(1, 3, 4\) ответ \(-1\). Чтобы заполнить первый шлюз нужно подождать \(4\) секунды, даже если открыты все трубы.
В шестом запросе можно открыть трубы в шлюзах \(1, 3\), и \(4\). Тогда через \(4\) секунды заполнятся шлюзы \(1\) и \(4\). Через \(1\) секунду \(1\) литр воды перельётся в шлюзы \(2\) и \(5\). Шлюз \(3\) будет заполнен своей трубой.
Аналогично во втором запросе можно открыть трубы в шлюзах \(1, 3\) и \(4\).
В пятом запросе можно открыть трубы в шлюзах с номерами \(1, 2, 3, 4\).
Тесты к этой задаче состоят из 5 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.
| Доп. ограничения | |||||||
| Группа | Баллы | \(n\) | \(q\) | \(v_i\) | \(t_j\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | – | Тесты из условия. |
| 1 | 17 | \(n \le 50\) | \(q \le 50\) | \(v_i \le 100\) | \(t_j \le 100\) | 0 | |
| 2 | 14 | – | – | – | – | – | Все \(v_i\) равны. |
| 3 | 19 | \(n \le 300\) | \(q \le 300\) | – | – | 0, 1 | |
| 4 | 24 | \(n \le 5000\) | \(q \le 5000\) | – | – | 0, 1, 3 | |
| 5 | 26 | – | – | – | – | 0 – 4 | |
5 4 1 5 4 1 6 1 6 2 3 4 5
-1 3 -1 -1 4 3
5 4 4 4 4 4 6 1 3 6 5 2 4
-1 -1 4 4 -1 5