--->
24 задач
<---
Источники
Первая сессия обычно доставляет много проблем. Одна из них заключается в том, что студенту нужен по крайней мере целый день, чтобы подготовиться к одному экзамену. В день одного экзамена к другому готовиться невозможно. Но основная проблема заключается в том, что студенты могут начать готовиться к i-му экзамену, не раньше чем за ti дней до него, иначе они все забудут. Глеб хочет начать готовиться к экзаменам как можно позже, но он собирается все экзамены сдать.
Помогите Глебу выбрать день начала подготовки к экзаменам.
Первая строка выходных данных содержит число экзаменов n (1 ≤ n ≤ 50 000). Следующие строки описывают экзамены. Каждое описание состоит из трех строк. Первая строка – это название экзамена (строка, содержащая только латинские буквы, длиной не более 10). Вторая строка – дата экзамена в формате dd.mm.yyyy. Третья строка содержит величину ti для этого экзамена (1 ≤ ti ≤ 100 000). Все экзамены проходят от 01.01.1900 до 31.12.2100. Не забудьте, что високосными считаются годы, которые делятся на 4 и не делятся на 100 или которые делятся на 400.
Выведите в формате dd.mm.yyyy, когда Глеб самое позднее сможет приступить к подготовке к экзаменам. Если расписание не позволяет подготовиться к каждому из экзаменов, то выведите слово Impossible.
3 Philosophy 29.06.2005 1 Algebra 30.06.2005 3 Physics 02.07.2005 10
27.06.2005
С окраины в центр города каждое утро по одному маршруту едут в трамвае 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 ≤ 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
Вам даны пары чисел \((a_i, b_i)\), Вам необходимо построить декартово дерево, такое что \(i\)-ая вершина имеет ключи \((a_i, b_i)\), вершины с ключом \(a_i\) образуют бинарное дерево поиска, а вершины с ключом \(b_i\) образуют кучу на минимум.
В первой строке записано число \(N\) — количество пар. Далее следует \(N\) (\(1 \le N \le 50\,000\)) пар \((a_i, b_i)\). Для всех пар \(\lvert a_i\rvert, \lvert b_i \rvert \le 30\,000\). \(a_i \ne a_j\) и \(b_i \neq b_j\) для всех \(i \ne j\).
Если декартово дерево с таким набором ключей построить возможно, выведите в первой строке YES, в противном случае выведите NO. В случае ответа YES, выведите \(N\) строк, каждая из которых должна описывать вершину. Описание вершины состоит из трёх чисел: номер предка, номер левого сына и номер правого сына. Если у вершины отсутствует предок или какой-либо из сыновей, то выводите на его месте число 0.
Если подходящих деревьев несколько, выведите любое.
7 5 4 2 2 3 9 0 5 1 3 6 6 4 11
YES 2 3 6 0 5 1 1 0 7 5 0 0 2 4 0 1 0 0 3 0 0
Реализуйте структуру данных, которая поддерживает множество \(S\) целых чисел, с котором разрешается производить следующие операции:
Исходно множество \(S\) пусто. Первая строка входного файла содержит \(n\) — количество операций (\(1 \le n \le 300\,000\)). Следующие \(n\) строк содержат операции. Каждая операция имеет вид либо «+ \(i\)», либо «? \(i\)». Операция «? \(i\)» задает запрос \(next(i)\).
Если операция «+ \(i\)» идет во входном файле в начале или после другой операции «+», то она задает операцию \(add(i)\). Если же она идет после запроса «?», и результат этого запроса был \(y\), то выполняется операция \(add((i + y) \bmod 10^9)\).
Во всех запросах и операциях добавления параметры лежат в интервале от \(0\) до \(10^9\).
Для каждого запроса выведите одно число — ответ на запрос.
6 + 1 + 3 + 3 ? 2 + 1 ? 4
3 4