Codeforces Round 751 (Div. 1) |
---|
Закончено |
У студентов одного неизвестного ПТУ нет обязательных занятий по физкультуре. Чтобы исправить это недоразумение, $$$q$$$ студентов решили самостоятельно записаться в спортзал. В спортзале действует система абонементов на посещения, в $$$i$$$-й из $$$n$$$ дней известна цена покупки абонемента $$$a_i$$$. Разрешается покупать более одного абонемента за день.
Купленный в день $$$i$$$ абонемент можно активировать как день $$$i$$$, так и в любой день позднее. Каждый из абонементов после активации будет действовать $$$k$$$ дней, то есть активированный в день $$$t$$$ абонемент будет действовать в дни с номерами $$$t, t + 1, \dots, t + k - 1$$$.
Известно, что $$$j$$$-й студент хочет посещать спортзал каждый день со дня $$$l_j$$$ по день $$$r_j$$$ включительно. Алгоритм похода в спортзал в некоторый день $$$i$$$ ($$$l_j \le i \le r_j$$$) любого из студентов выглядит следующим образом:
Заметим, что ни один студент не придет в спортзал раньше дня $$$l_j$$$, а потому каждый студент обязательно купит не менее одного абонемента в день $$$l_j$$$.
Помогите каждому студенту посчитать, какую минимальную сумму ему придется потратить, чтобы посещать зал в свои дни.
В первой строке заданы три целых числа $$$n$$$, $$$q$$$ и $$$k$$$ ($$$1 \le n, q \le 300\,000$$$; $$$1 \le k \le n$$$) — количество дней, количество студентов и длительность любого абонемента.
Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — стоимость одного абонемента в соответствующий день.
В следующих $$$q$$$ строках заданы два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — отрезок дней, в которые соответствующий студент хочет посещать спортзал.
Для каждого студента выведите минимальную сумму, необходимую ему для посещения спортзала в выбранный отрезок дней.
7 5 2 2 15 6 3 7 5 6 1 2 3 7 5 5 7 7 3 5
2 12 7 6 9
Рассмотрим как нужно покупать абонементы каждому из студентов:
Название |
---|