--->
90 задач
<---
Источники
Петя в очередной раз купил себе набор из кубиков. На этот раз он выстроил из них настоящую крепость — последовательность из N столбиков, высота каждого столбика составляет Ai кубиков.
Вскоре ему стало интересно, насколько его крепость защищена от жуликов и воров. Для этого он ввел понятия башни. Башней называется любая последовательность из K столбиков подряд (где K — любимое число Пети). Защищенность башни определяется как суммарная высота всех столбиков этой башни (чем она больше, тем громаднее и ужаснее она кажется), умноженная на минимум высоты столбиков башни (т.к. враги, очевидно, будут пытаться проникнуть через самое слабое место башни). Неприступность крепости определяется как сумма защищенностей каждой из башен.
Петя решил как можно скорее посчитать, какова же неприступность его крепости. Однако вскоре он понял, что недостаточно знать высоту каждого из столбиков. В зависимости от того, как сгруппировать столбики в башни, получится разный результат. В различных вариантах группировки часть столбиков могут не принадлежать ни одной из башен. Разумеется, Петя выберет то разбиение на башни, при котором неприступность будет максимальна.
Петя успешно справился со своей задачей, но теперь Правительство Флатландии решило защитить свой горный курорт. Правительство уже построило крепость из кубиков (просто кубики были побольше). Теперь вы должны помочь Правительству посчитать неприступность этой крепости. Единственная трудность состоит в том, что у Правительства было очень много денег, и поэтому крепость была построена очень длинная.
В первой строке входного файла содержатся число N — количество столбиков в крепости и число K — любимое число Пети (1 ≤ K ≤ N ≤ 100 000). Далее на следующей строке содержатся N целых чисел, обозначающих Ai (1 ≤ Ai ≤ 106).
На первой строке выведите число Q — количество башен в оптимальном разбиении. Далее выведите Q чисел — номера первых столбиков каждой башни.
1 1 1
1 1
2 1 1 1000000
2 1 2
8 3 1 2 3 4 1 6 7 8
2 2 6
Цифровой поезд нового поколения состоит из вагонов, содержащих по \(N\) мест для пассажиров. Все места расположены вдоль вагона и пронумерованы от \(1\) до \(N\). Вход в вагон расположен левее места \(1\), а места \(1, 2, \ldots, N\) расположены правее от входа в соответствующем порядке. \(N\) пассажиров готовятся сесть в поезд. Каждый заходящий в вагон характеризуется номером места \(A_i\) и своей массой \(B_i\). Когда пассажир идет по вагону от входа до своего места, некоторые пассажиры, которые сели ранее, мешают ему пройти. Пассажир испытывает неудобство, каждый раз проходя мимо человека массы большей, чем у него самого. Суммарным неудобством пассажира при посадке называется количество раз, когда он испытывал неудобство при движении к своему месту от входа в вагон. Ваша задача — по заданному порядку посадки пассажиров найти суммарное неудобство каждого.
Входной файл состоит из одного или нескольких наборов входных данных. Каждый набор начинается с целого числа \(N\; (1 \leq N \leq 100\,000)\) — количества мест (пассажиров). Далее набор входных данных содержит пары целых чисел \(A_i, B_i\; (1 \leq A_i \leq N, 1 \leq B_i \leq 10^9)\). Все числа \(A_i\) и \(B_i\) различны между собой. То есть номера мест пассажиров образуют перестановку. Пассажиры садятся в поезд именно в том порядке, в котором они заданы во входном файле. Количество наборов входных данных не превосходит \(5\).
Выведите ответ на каждый набор входных данных. Каждый ответ должен состоять из последовательности \(N\) целых чисел \(P_1, P_2, \ldots, P_N\), где \(P_i\) — суммарное неудобство \(i\)-го пассажира.
3 1 2 2 3 3 1 2 1 1 2 2
0 0 2 0 0
Город Прямой Рог, который пока что не находится на территории Российской Федерации, представляет собой одну прямую улицу. В городе работает компания, которая занимается доставкой товаров. Для удобства, адреса доставки представлены в виде чисел, которые задают расстояние от офиса компании. Положительные числа в одну сторону, а отрицательные – в другую. Заказы на доставку выполняются компанией последовательно, в том порядке, в котором они были заданы. В компании работает два курьера. В начале рабочего дня заказы распределяются между ними, и каждый отправляется по своему маршруту. Компании необходимо так спланировать распределение заказов, чтобы суммарное расстояние, которое будет пройдено курьерами на момент выполнения последнего заказа, была минимальным. Напишите программу, которая по расстояниям адресатов от офиса компании находит наименьшее суммарное расстояние, которое пройдут ее работники.
Первая строка входных данных содержит целое число N (1 ≤ N ≤ 100 000) — количество заказов. Далее следует N строк, каждая из которых содержит одно целое число — расстояние от офиса до адресата. Если расстояние положительное — то адресат находится в одной части города относительно офиса компании, а если отрицательное, то в другой. Расстояния по модулю не превышают 108.
Единственная строка должна содержать одно целое число — минимально возможное суммарное расстояние, которое пройдут оба работника компании.
5
1
-1
2
-2
3
5
Все элементы магнитной мозаики фирмы «ABBYY» имеют прямоугольную форму. Два элемента можно соединить только в том случае, если у них совпадает хотя бы один из размеров: длина, ширина, или и то, и другое. Магнитные элементы поворачивать и переворачивать нельзя. Пару элементов мозаики, которые нельзя соединить, назовем негармоничной. Например, пара 1 × 2 и 2 × 3 является негармоничной, а пары 2 × 3 и 1 × 3 или 2 × 3 и 2 × 3 являются гармоничными. Дизайнеры «ABBYY» выложили все элементы мозаики в ряд, не соединяя их между собой. Назовем набором несколько подряд лежащих элементов мозаики в этом ряду. Они выбрали несколько наборов элементов, которые хотят оставить для создания инсталляции. Для каждого такого набора им нужно выяснить, есть ли в нем негармоничная пара элементов. Требуется написать программу, которая для различных наборов подряд лежащих элементов мозаики определит номера элементов, образующих негармоничную пару, или сообщит, что такой пары нет.
В первой строке входного файла записано одно число N – количество элементов, из которых состоит мозаика (2 ≤ N ≤ 100 000). В следующих N строках записаны по два целых числа Ai и Bi , задающих длину и ширину i-го элемента мозаики соответственно (1 ≤ Ai, Bi ≤ 109, 1 ≤ i ≤ N). В (N + 2)-й строке записано одно целое число K – количество наборов, в каждом из которых нужно определить номера двух негармоничных элементов (1 ≤ K ≤ 100 000). В следующих K строках записаны пары целых чисел N1 и N2 – номера первого и последнего элементов набора соответственно, в котором необходимо найти два негармоничных элемента мозаики (1 ≤ \(N_1\) < \(N_2\) ≤ N).
Выходной файл должен содержать K строк, каждая из которых содержит два разделённых пробелом числа – номера элементов мозаики, образующих негармоничную пару в соответствующем наборе. Если решений несколько, можно вывести любое из них. Если в наборе негармоничная пара отсутствует, требуется вывести в соответствующей строке 0 0.
Данная задача содержит четыре подзадачи. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы успешно пройдены.
4 2 2 1 2 1 3 2 3 2 2 3 2 4
0 0 4 2