См. «Двоичная куча (пирамида). Пирамидальная сортировка. Приоритетная очередь» (PDF), стр. 14, задача 9.
Ограничение времени – 1 секунда
С окраины в центр города каждое утро по одному маршруту едут в трамвае N человек. За долгое время поездок они достаточно хорошо узнали друг друга. Чтобы никому не было обидно, они захотели решить, кто из них и между какими остановками маршрута должен сидеть, а кто должен стоять. Все остановки пронумерованы от 1 до P.
Один из пассажиров оказался знатоком теории математического моделирования. Он предложил рассмотреть значение суммарного удовлетворения пассажиров. Для каждого i-го пассажира он оценил две величины — ai и bi. Если в течение одного переезда между остановками пассажир сидит, то к суммарному удовлетворению прибавляется ai, если же он стоит, то прибавляется bi.
Всего в трамвае M сидячих мест. Вставать и садиться пассажиры могут мгновенно на любой остановке. Кроме того, некоторые пассажиры предпочитают ехать стоя, даже если в трамвае есть свободные места (для них ai < bi).
Требуется написать программу, которая вычисляет значение максимально достижимого суммарного удовлетворения, если для каждого i-го пассажира известны величины ai и bi, а также номера остановок, на которых он садится и выходит из трамвая.
Первая строка входного файла содержит разделенные пробелом три целых числа N, M и P — число пассажиров, число сидячих мест и число остановок на маршруте соответственно (1 ≤ N, M, P ≤ 100 000; 2 ≤ P).
Каждая из следующих N строк содержит информацию об очередном пассажире в виде четырех целых чисел ai, bi, ci, di:, где первые два числа определяют вклад в параметр счастья, третье – номер остановки, на которой пассажир садится в трамвай, и последнее – номер остановки, на которой он выходит из трамвая (−106 ≤ ai, bi ≤ 106; 1 ≤ ci < di ≤ P).
В выходной файл необходимо вывести одно целое число — максимальное суммарное удовлетворение, которого могут добиться пассажиры.
Комментарий к примеру тестов
Максимальное суммарное довольство достигается следующим образом:
На первой остановке входят и садятся второй и третий пассажиры;
На второй остановке входят первый и четвертый пассажиры, второй уступает место первому;
На третьей остановке встают и выходят первый и третий пассажиры, второй и четвертый садятся на их места;
На четвертой остановке выходят второй и четвертый пассажиры.
Разбалловка для личной олимпиады
Тест 1 — из условия. Оценивается в 0 баллов.
Тесты 2-31 — числа M, N, P не превосходят 100. Группа тестов оценивается в 60 баллов.
Тесты 32-41 — число P не превосходит 100. Группа тестов оценивается в 20 баллов (вместе с предыдущей группой — 80 баллов).
Тесты 42-51 — дополнительных ограничений нет. Группа тестов оценивается в 20 баллов (вместе с предыдущими группами — 100 баллов).
Баллы начисляются за прохождение всех тестов группы и всех тестов предыдущих групп.
4 2 4 10 -10 2 3 -1 -3 1 4 6 -6 1 3 7 4 2 4
28
В новых элитных электричках каждому пассажиру положено сидячее место. Естественно, количество сидячих мест ограничено и на всех их может не хватить. Маршрут электрички проходит через N+1 станция, занумерованные от 0 до N. Когда человек хочет купить билет, он называет два числа x и y – номера станций, откуда и куда он хочет ехать. При наличии хотя бы одного сидячего места на этом участке на момент покупки ему продается билет, иначе выдается сообщение «билетов нет» и билет не продается. Ваша задача – написать программу, обслуживающую такого рода запросы в порядке их прихода.
В первой строке содержаться три числа N – количество станций (1 ≤ N ≤ 200 000), K – количество мест в электричке (1 ≤ K ≤ 1000) и M – количество запросов (1 ≤ M ≤ 100 000). В следующих M строках описаны запросы, каждый из которых состоит из двух чисел x и y (0 ≤ x < y <= N).
На каждый запрос ваша программа должна выдавать результат в виде числа 0 если билет не продается и 1 если билет был продан. Каждый результат должен быть на отдельной строке
5 2 4 0 4 1 2 1 4 2 4
1 1 0 1
В одной военной части решили построить в одну шеренгу по росту. Т.к. часть была далеко не образцовая, то солдаты часто приходили не вовремя, а то их и вовсе приходилось выгонять из шеренги за плохо начищенные сапоги. Однако солдаты в процессе прихода и ухода должны были всегда быть выстроены по росту – сначала самые высокие, а в конце – самые низкие. За расстановку солдат отвечал прапорщик, который заметил интересную особенность – все солдаты в части разного роста. Ваша задача состоит в том, чтобы помочь прапорщику правильно расставлять солдат, а именно для каждого приходящего солдата указывать, перед каким солдатом в строе он должен становится.
Первая строка содержит число N – количество команд (1 ≤ N ≤ 50 000). В каждой следующей строке содержится описание команды: число 1 и X если солдат приходит в строй (X – рост солдата, натуральное число до 100 000 включительно) и число 2 и Y если солдата, стоящим в строе на месте Y надо удалить из строя. Солдаты в строе нумеруются с нуля.
На каждую команду 1 (добавление в строй) вы должны выводить число K – номер позиции, на которую должен встать этот солдат (все стоящие за ним двигаются назад). Выводите числа по одному в строке.
5 1 100 1 200 1 50 2 1 1 150
0 0 2 1
Служба электроснабжения проводит мониторинг уровня снега, лежащего на ЛЭП Нью-Васюки - Москва. Вся ЛЭП разбивается на участки опорами. Снег имеет свойства падать на какой-либо интервал ЛЭП, если там уже лежал какой-либо снег, то высота снежного покрова на этом участке суммируется. Также снег имеет тенденцию таять на участке трассы в результате оттепели, при этом известно, что не бывает сугробов отрицательной высоты. Энергетикам крайне важно уметь узнавать суммарную высоту снежного покрова на некоторых последовательных участках, чтобы знать вероятность обрыва проводов.
В первой строке входного файла содержатся два числа: N – (1 ≤ N ≤ 10 000) и M – количество команд (1 ≤ M ≤ 50 000). Каждая команда имеет вид “1 L R S”, что означает, что на участок с L-ой опоры по R-ую опору выпало S сантиметров снега (S может быть и отрицательным, тогда это означает, что такое количества снега растаяло), или “2 L R” – запрос суммарной высоты снега на участке с L-ой опоры по R-ую. Опоры нумеруются от 0 до N. Гарантируется, что для запросов вида “1 L R S” при S < 0 на каждом участке между опорами L и R уровень снега составляет не менее S.
На каждую команду 2 (запрос) вы должны выводить число K – суммарную высоту снежного покрова, лежащего на проводах с L-ой опоры по R-ую. Каждое число должно выводиться на новой строке. Известно, что в процессе работы суммарное количество снега на любом интервале не превышает 231.
10 5 1 0 9 10 1 1 5 -3 2 4 8 1 0 6 25 2 0 2
37 67