--->
90 задач
<---
Источники
У Коли сегодня день рождения! По этому случаю он решил после олимпиады сходить с друзьями в парк аттракционов. И какая удача — можно купить групповой билет сразу на всех, всего за S рублей!
Конечно, скидываться придется всем поровну. То есть, если Коля позовет k своих друзей, то каждому придется заплатить S / (k + 1) рублей (да, сам Коля тоже должен внести свою долю). При этом S не обязательно должно делиться на k + 1: главное — купить билет, а между собой друзья уж как-нибудь договорятся.
Всего у Коли n друзей, при этом i-й из них готов пойти с Колей в парк, если доля, которую ему придется заплатить не больше bi (больше денег у него просто с собой нет) и не меньше ai (иначе он решит, что Колин день рождения — это скучно, и пойдет играть в волейбол с Сережей).
Так что может так получиться, что всех позвать не удастся. Ну и ладно. Для каждого своего друга Коля знает число fi — количество веселья, который тот произведет, если его позвать.
Помогите Коле выбрать подмножество друзей, которых Коля должен позвать с собой, чтобы максимизировать суммарное веселье.
В первой строке входного файлы содержится два целых числа: n и S (1 ≤ n ≤ 100000, 0 ≤ S ≤ 109) — количество друзей Коли и стоимость билета. В следующих n строках содержится по три целых числа: в i-й из этих строк находятся числа ai, bi и fi (0 ≤ ai ≤ bi ≤ S, 0 ≤ fi ≤ 109). Они означают, что i-го друга можно позвать на вечеринку, если доля, которую ему придется заплатить, лежит между ai и bi, и он произведет fi веселья.
В первой строке выходного файла выведите два числа: k (количество приглашенных на вечеринку друзей) и F (максимальное суммарное веселье, которое можно получить). Во второй строке выведите k чисел — номера друзей, которых нужно пригласить
4 10 4 5 40 2 4 30 2 6 10 3 5 20
2 50 2 4
Злобный учитель в MШП любит мучить детей сложными задачками. А если дети эти задачки не решают, учитель подвергает их самым жестоким наказаниям. На этот раз он придумал такую задачу:
Рейтинг всех учеников МШП записан в массив A
Запросы учителя таковы:
Помогите бедным ученикам МШП избежать зверского наказания за нерешение задачи на этот раз.
В первой строке входного файла записано число N (1 ≤ N ≤ 500000) – количество учеников в МШП. Во второй строке записано N чисел – их рейтинги, числа по модулю не превосходящие 1000 (по количеству задач, которые ученик решил или не решил за время обучения). В третьей строке записано число M (1 ≤ M ≤ 50000) – количество запросов. Каждая из следующих M строк содержит описания запросов:
UPDATE i x – обновить i-ый элемент массива значением x (1 ≤ i ≤ N, |x| ≤ 1000)
QUERY l r – найти длину максимальной последовательности из нулей на отрезке с l по r. (1 ≤ l ≤ r ≤ N)
В выходной файл выведите ответы на запросы QUERY в том же порядке, что и во входном файле
5 328 0 0 0 0 5 QUERY 1 3 UPDATE 2 832 QUERY 3 3 QUERY 2 3 UPDATE 2 0
2 1 1
На экране расположены прямоугольные окна, каким-то образом перекрывающиеся (со сторонами, параллельными осям координат). Вам необходимо найти точку, которая покрыта наибольшим числом из них.
В первой строке входного файла записано число окон n (1 ≤ n ≤ 50 000). Следующие n строк содержат координаты окон x(1, i) y(1, i) x(2, i) y(2, i), где (x(1, i), y(1, i)) — координаты левого верхнего угла i-го окна, а (x(2, i), y(2, i)) — правого нижнего (на экране компьютера y растет сверху вниз, а x — слева направо). Все координаты — целые числа, по модулю не превосходящие 106.
В первой строке выходного файла выведите максимальное число окон, покрывающих какую-либо из точек в данной конфигурации. Во второй строке выведите два целых числа, разделенных пробелом — координаты точки, покрытой максимальным числом окон. Окна считаются замкнутыми, т. е. покрывающими свои граничные точки.
2 0 0 3 3 1 1 4 4
2 1 3
1 0 0 1 1
1 0 1
4 0 0 1 1 0 1 1 2 1 0 2 1 1 1 2 2
4 1 1
5 0 0 1 1 0 1 1 2 0 0 2 2 1 0 2 1 1 1 2 2
5 1 1
Джек нашел \(N\) камней и упорядочил их в порядке возрастания их массы. Массы всех камней различны. Самый легкий камень получил номер 1, следующий 2 и так далее, самый тяжелый получил номер \(N\).
У Джека есть чашечные весы и он решил положить все камни на них в каком-то порядке. Известен порядок, в котором он будет класть камни, и какой камень на какую чашу попадет.
Ваша задача — определить состояние весов после добавления каждого камня. Точные массы камней не известны — даются только их номера.
Первая строка содержит целое число \(N\) (1 \(\le\) \(N\) \(\le\) 100000).
Каждая из следующих \(N\) строк содержит по два целых числа: \(R\) (1 \(\le\) \(R\) \(\le\) \(N\)) и \(S\) (1 \(\le\) \(S\) \(\le\) 2). \(R\) номер камня, который будет положен на чашу \(S\). Все \(R\) будут различны.
Выведите \(N\) строк по одной для каждого камня. Если после добавления соответствующего камня чаша 1 тяжелее, выведите “<”. Если сторона 2 тяжелее, выведите “>”. Если невозможно определить, в каком состоянии будут весы, выведите “?”.
5 1 2 3 1 2 1 4 2 5 1
< > > ? >
Как известно, автобус должен ходить по расписанию. И Иннокентий, используя свои многочисленные связи в магазине плитки, совершил невозможное: по маршруту теперь курсируют целых \(M\) автобусов, и на каждой остановке висит свое расписание, которое представляет собой набор из \(M\) времен. Плиточный магнат является крупным авторитетом в городе, поэтому расписание соблюдается: от каждой остановки ровно в каждое из указанных времен отправляется автобус. Казалось, что проблема общественного транспорта навсегда решена...
Однако, дьявол кроется в деталях. Действительно, автобусы отправляются с остановок в нужные времена, но никто не гарантирует, что между остановками не произойдет обгон, и автобус, который отправился от предыдущей остановки раньше, не отправится со следующей гораздо позже, при этом не нарушая условия, что в каждое из указанных в расписании времен какой-то автобус отправляется.
Иннокентий решил оценить масштабы трагедии. Для этого он попросил каждого из Q своих друзей сообщить маршрут, по которому они добираются до места работы. Каждый маршрут описывается тремя числами \(u_i\), \(v_i\), \(w_i\): \(u_i\) — это номер остановки, ближайшей к дому i-го друга, \(v_i\) — номер остановки, ближайшей к его работе, а \(w_i\) — номер автобуса,на котором i-й друг едет из дома на работу. При этом с точки зрения i-го друга автобусы нумеруются от \(1\) до \(M\) в том порядке, в котором они отправляются с остановки \(u_i\).
Иннокентий просит вас независимо для каждого друга определить, насколько поздно тот может доехать до конечной остановки своего маршрута.
В первой строке входных данных содержатся два целых числа \(N\) и \(M\) — количество остановок и количество автобусов соответственно (\(2 \le N * M \le 150 000\)). В следующей строке содержатся \(N-1\) целых чисел \(travel_1\), . . . , \(travel_{N-1}\), где \(travel_i\) — минимальное время, необходимое для перемещения между остановками i и i + 1 (\(1 \le travel_i \le 10^9\)).
В следующих \(N\) строках содержатся описания расписаний, каждое из которых представляет собой отсортированный по возрастанию список из \(M\) различных целых чисел \(t_i\) — времен, в которые автобусы должны отправляться с соответствующей остановки (\(1 \le t_i \le 10^9\)).
В следующей строке содержится число T — тип теста (1 или 2). Если T = 1, то это — обычный тест. Тогда на следующей строке содержится целое число Q — количество опрошенных друзей Иннокентия (\(1 \le Q \le 150 000 \)). Далее в Q строках содержатся описания маршрутов друзей, каждое из которых состоит из трех целых чисел \(u_i\), \(v_i\) и \(w_i\): номеров остановок, где начинается и заканчивается поездка i-го друга, и номер автобуса в расписании остановки ui, на котором эта поездка совершается (\(1 \le u_i < v_i \le N, 1 \le w_i \le M\)).
\textbf{Обратите внимание} : дальнейшее описание относится только к последней группе тестов. Если T = 2, то это — тест-серия. Тогда на следующей строке содержатся три целых числа — A, B и K (\(1 \le A, B \le 10^3 , 1 \le K \le 150\)).
В \t{тесте-серии} у Иннокентия Q = (N -1)·M ·K друзей. На каждой из N - 1 остановок, кроме последней, проживает ровно M * K друзей, причем для каждого \(w\) от 1 до M есть ровно K друзей, которые уезжают с этой остановки w-м автобусом.
Остановки, до которых едут K друзей, уезжающих с u-й остановки w-м автобусом, определяются следующим образом. Задается последовательность чисел \(q_i\): \(q_1\) = A, \(q_2\) = B, для i > 2 \(q_i\) = u * \(q_{i-1}\) + w * \(q_{i-2}\) + 42. Тогда i-й из этих K друзей будет ехать до остановки с номером \(v_i\) = u + 1 + (\(q_i\) mod (N - u)), где mod обозначает операцию взятия остатка от деления.
Если это обычный тест, то выведите для каждого друга в отдельной строке единственное целое число - искомое максимальное время прибытия на конечную остановку в его маршруте. Если это тест-серия, то выведите единственное целое число — остаток от деления суммы максимальных времен прибытия для всех друзей Иннокентия на \(2^{32}\).
Приведем пояснение ко второму тесту из условия.
Это \textbf{тест-серия}. В нем у Иннокентия 5 · 4 · 2 = 40 друзей. Например, с первой остановки вторым автобусом уезжают ровно пять друзей. Поясним, как в этом тесте для них определить конечные остановки. u = 1, w = 2. Строим последовательность \(q_i\): \(q_1\) = 9, \(q_2\) = 10, \(q_3\) = 1 · 10 + 2 · 9 + 42 = 70, \(q_4\) = 1 · 70 + 2 · 10 + 42 = 132, \(q_5\) = 1 · 132 + 2 · 70 + 42 = 314. По ней восстанавливаются конечные остановки для этих пяти друзей Иннокентия: \(v_1\) = 1 + 1 + (9 mod 4) = 3, \(v_2\) = 1 + 1 + (10 mod 4) = 4, \(v_3\) = 1 + 1 + (70 mod 4) = 4, \(v_4\) = 1 + 1 + (132 mod 4) = 2, \(v_5\) = 1 + 1 + (314 mod 4) = 4.
Тесты к этой задаче состоят из шести групп. Каждая группа, кроме нулевой, оценивается в 20 баллов. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов \textbf{предыдущих групп}, исключая тесты из условия. В группах тестов с первой по четвертую включительно вам предлагаются только обычные тесты.
0. Тесты 1—2. Тесты из условия, оцениваются в ноль баллов.
1. Тесты 3—12. В тестах этой группы \(N = 2, M \le 1 000, Q \le 1 000\).
2. Тесты 13—22. В тестах этой группы \(N = 2, M \le 75 000, Q \le 75 000\).
3. Тесты 23—37. В тестах этой группы \(N * M \le 150 000, N * Q \le 150 000\).
4. В тестах этой группы \(N * M \le 150 000, Q \le 150 000\).
5. В этой группе вам предлагаются только тесты-серии. Другие дополнительные ограничения отсутствуют.
2 3 1 1 10 21 11 21 31 1 3 1 2 1 1 2 2 1 2 3
21 21 31
5 2 2 5 3 4 1 3 3 5 10 11 13 14 18 23 2 9 10 5
667