Сортировка событий

18 задач

Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.

РейтингЛюбой до 800 800–1199 1200–1599 1600+Без рейтинга

СначалаПодходящие Новые Популярные Простые Сложные

Точка максимального покрытия#94329

На числовой прямой нарисованы \(n\) отрезков. Концы отрезков заданы целыми числами. Точка \(x\) считается принадлежащей отрезку \([s, f]\), если \(s \le x \le f\) (концы включены).

Найдите такую целую точку \(x\), которой одновременно принадлежит максимальное количество данных отрезков. Если таких точек несколько, выведите наименьшую из них.

Формат входных данных

В первой строке записано целое число \(n\) (\(1 \le n \le 10^5\)) — количество отрезков.

В каждой из следующих \(n\) строк записаны два целых числа \(s_i\) и \(f_i\) (\(-10^9 \le s_i \le f_i \le 10^9\)) — концы очередного отрезка.

Формат выходных данных

Выведите два целых числа через пробел: максимальное количество отрезков, накрывающих одну точку, и наименьшую целую точку, в которой этот максимум достигается.

Примечание

В первом примере отрезки \([0,1]\), \([0,2]\), \([1,2]\). Точка \(x = 1\) принадлежит всем трём отрезкам, и это наименьшая такая точка.

Во втором примере точка \(x = 1\) принадлежит двум отрезкам: \([0,1]\) и \([1,3]\). Это максимум, достигаемый раньше всего на прямой.

Сортировка событий

—Войти и решать

Load Balancing#90419

Коровы Фермера Джона стоят в различных точках \((x_1, y_1) \ldots (x_n, y_n)\) его поля (\(1 \leq N \leq 100,000\), все \(x_i\) и \(y_i\) - положительные нечётные целые числа, не превышающие \(1,000,000\). ФД хочет разделить своё поле изгородью бесконечной длины с севера на юг, описываемой уравнением \(x=a\) (\(a\) - чётное целое, так обеспечивается, что изгородь не пройдёт через позицию ни одной коровы). Также он хочет построить изгородь бесконечной длины с востока на запад, которая описывается уравнением \(y=b\), где \(b\) - чётное целое. Эти две изгороди пересекаются в точке \((a,b)\), и вместе делят поле на четыре региона.

ФД хочет выбрать \(a\) и \(b\) так, чтобы получить "сбалансированное" количество коров во всех регионах, т.е. чтобы не было региона, который содержит слишком много коров. Пусть \(M\) - максимальное количество коров в этих четырёх регионах, ФД хочет, чтобы \(M\) было как можно меньше. Помогите ФД определить это минимально возможное значение для \(M\).

ФОРМАТ ВВОДА (файл balancing.in):

Первая строка ввода содержит одно целое число, \(N\). Каждая из следующих \(n\) строк содержит местоположение одной коровы, указанное её координатами \(x\) и \(y\).

ФОРМАТ ВЫВОДА (файл balancing.out):

Выведите минимально возможное значение \(M\), которое может достичь ФД оптимальным расположением изгородей.

Сортировка событий

—Войти и решать

Stampede#90377

Problem 1: Stampede [Brian Dean]

N коров (1 <= N <= 50,000) Фермера Джона стоят вдоль дороги перед
фермой – предстоит забег, чтобы узнать какая корова самая быстрая.

Каждая корова представлена горизонтальным отрезком одиночной длины,
с началом в левой угловой точке в момент времени t=0. Например,
(-3,6) обозначает корову, которая в момент времени 0 представлена отрезком
из (-3,6) в (-2,6). Каждая корова движется вправо (в направлении + по оси x),
на некоторой скорости указанной количеством времени, требуемым для того,
чтобы переместиться на единицу расстояния вправо.

ФД для того, чтобы определить, какие из его коров участвуют в гонке,
расположился в точке (0,0) и смотрит в направлении +y.
ФД видит только ближайшую к себе корову. То есть корова может быть
не видима, если другая корова находится «перед ней» всё время пока
пересекает «линию взгляда» ФД.

Пожалуйста, определите количество коров, которые ФД увидит во время
гонок.

Формат входных данных

Первая строка ввода содержит N. Каждая из последующих N строк
описывает одну корову тремя целыми числами x y r, определяющими
левую точку коровы (x,y) в момент времени t=0 и постоянную скорость
её движения право – r, то есть что эта корова перемещается на 1
единицу расстояния за r единиц времени. X находится в диапазоне -1000..1,
а y находится в диапазоне 1..1,000,000 (и различается для каждой коровы,
чтобы предотвратить коллизии), и значение r находится в диапазоне 1..1,000,000.

Формат выходных данных

Одно целое число, указывающее количество коров, которых ФД
сможет увидеть за время гонки от момента времени 0 и далее.

Примечание
ФД сможет увидеть коров 1 и 2 и не сможет увидеть корову 3.

Сортировка событий

—Войти и решать

Grass Segments#90276

Беси посадила траву на положительной вещественной прямой. У неё есть \(N\) (\(2\le N\le 2\cdot 10^5\)) различных сортов травы. И она посадит траву \(i\)-го сорта на интервале \([\ell_i, r_i]\) (\(0 < \ell_i < r_i \leq 10^9\)).

Известно, что сорт \(i\) растёт лучше, если есть некоторый сорт \(j\) (\(j\neq i\)) такой, что сорт \(j\) и сорт \(i\) перекрываются на длину не менее \(k_i\) (\(0 < k_i \leq r_i - \ell_i\)). Беси хочет для каждого сорта \(i\) вычислить количество таких of \(j\neq i\), что сорты \(j\) и \(i\) перекрываются на длину не менее \(k_i\).

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит число \(N\).

Каждая из последующих \(N\) строк содержит три разделённых одиночными пробелами целых числа \(\ell_i\), \(r_i\), \(k_i\).

ФОРМАТ ВЫВОДА (на экран / stdout):

Ответы для всех сортов на отдельных строках.

SCORING:

Тесты 4-5: \(N \leq 5000\)
Тесты 6-11: \(k\) одинаковое для всех интервалов
Тесты 12-20: Нет дополнительных ограничений..

В дополнение, в тестах 5, 7, ..., 19, \(r_i \leq 2N\) for all \(i\).

Автор: Benjamin Qi

Отрезки Префиксные суммы(минимумы, ...)Сортировка событий

—Войти и решать

Lifeguards#90021

Фермер Джон открыл бассейн для своих коров, чтобы они там отдыхали и потом давали больше молока.

Чтобы обеспечить безопасность, он нанял \(N\) коров спасателями, каждый из которых работает в течение некоторого интервала времени в течение дня. Для простоты, бассейн открыт с момента времени \(t=0\) до момента времени \(t = 1,000,000,000\) каждый день. Поэтому каждый интервал может быть описан двумя целыми числами - временем начала и конца работы спасателя. Например, спасатель, начинающий в момент времени \(t = 4\) и завершающий в момент времени \(t = 7\), покрывает интервал в три единицы времени.

К несчастью, ФД нанял на одного спасателя больше чем может платить зарплату. При условии, что он должен уволить одного спасателя, какой максимальный интервал времени, будет покрыт оставшимися спасателями? Интервал времени покрыт, если присутствует хоть один спасатель в это время.

ФОРМАТ ВВОДА (файл lifeguards.in):

Первая строка ввода содержит \(N\) (\(1 \leq N \leq 100,000\)). Каждая из последующих \(N\) строк описывает интервалы работы спасателей двумя целыми числами в интервале \(0 \ldots 1,000,000,000\), задающими начало и конец работы спасателя. Все числа концы интервалов - различны. Сами интервалы могут перекрываться.

ФОРМАТ ВЫВОДА (файл lifeguards.out):

Выведите одно целое число - максимальное количество времени, которое останется покрытым, если ФД уволит одного спасателя.

Сортировка событий

—Войти и решать

Convention II#89998

На съезд прибыли коровы со всего мира.

На маленькой полянке есть очень редкая трава. Как результат, все \(N\) (\(1 \leq N \leq 10^5\)) коров, прибывших на конференцию, хотят попробовать эту траву. Они выстраиваются в огромную очередь, поскольку на полянке может быть в один момент времени только одна корова.

Фермер Джон знает время \(a_i\), в которое корова \(i\) планирует прибыть на это пастбище, а также количество времени \(t_i\), которое эта корова собирается провести на этом специальном пастбище. После того, как корова \(i\) начинает есть траву, она делает это всё время \(t_i\), в течение которого все вновь прибывшие коровы вынуждены ждать. Если несколько коров ждут, когда пастбище освободится, корова с более высоким старшинством будет следующей на поедание травы. С этой целью корова, которая прибывает прямо, когда другая корова завершает есть траву, называется "ожидающей". Аналогично, если некоторое количество коров прибывает в один и тот же момент времени, и никакая корова не ест, то корова с более высоким старшинством принимается за еду.

Помогите ФД вычислить максимальное количество времени, которое придётся ждать любой корове (между временем \(a_i\) и временем, когда она начнёт есть).

ФОРМАТ ВВОДА (файл convention2.in):

Первая строка ввода содержит \(N\). Каждая из последующих \(N\) строк указывает детали \(N\) коров в порядке старшинства (более старшая корова - первая). Каждая строка содержит \(a_i\) и \(t_i\) для одной коровы. \(t_i\) - положительные целые числа, не превышающие \(10^4\), \(a_i\) - положительные целые числа, не превышающие \(10^9\).

ФОРМАТ ВЫВОДА (файл convention2.out):

Выведите наибольшее потенциальное время ожидания среди всех коров.

Сортировка событий

—Войти и решать

Goldilocks and the N Cows#89899

На ферме Goldilocks имеется N коров (1 <= N <=20,000), очень чувствительных к температуре.
Для каждой коровы указывается диапазон температур A(i)..B(i), которые допустимы. (0 <= A(i) <= B(i) <= 1,000,000,000). Если температура TB(i), то этой корове слишком жарко и она производит Z единиц молока. Y всегда больше чем и X, и Z.
По данным X Y Z а также наборам допустимых температур для каждой коровы, определите максимальное количество молока, которое может получить Goldilocks установкой оптимальной температуры (единой для всех коров).
Z Y Z – целые в диапазоне от 0 до 1000, а температура может быть установлена в любое целое значение.
Частичное оценивание: Из десяти тестов для этой задачи в тестах 1..4 B(i)<=100 для каждой коровы, и в тестах 1..6 значение N не превышает 1000.
PROBLEM NAME: milktemp
Формат входных данных
* Строка 1: Четыре разделённых пробелом целых числа: N X Y Z.
* Строки 2..1+N: Строка 1+i содержит два разделённых пробелом целых числа : A(i) B(i).
Формат выходных данных
* Строка 1: Максимальное количество молока, которое можно получить установкой оптимальной температуры в амбаре.

Примечание
Если установить температуру в 7 или 8, то коровам с номерами 1 и 4 будет комфортабельно, корове 2 будет жарко, а корове 3 – холодно. Всего будет произведено 31 единица молока.

Сортировка событий

—Войти и решать

Painting the Fence#89885

Корова Беси красит забор Фермеру Джону. Беси начинает в позиции 0 и выполняет последовательность из N инструкций. (1 <= N <= 100,000) вида "10 L", что означает покрасить 10 единиц влево и "15 R", что означает покрасить 15 единиц вправо.
Бесси может уйти не далее чем на 1,000,000,000 единиц от исходной точки.
По имеющей инструкции ФД хочет узнать область забора, которая покрашена как минимум K слоями краски.
PROBLEM NAME: paint
Формат входных данных
* Строка 1: Целые N и K
* Строки 2..1+N: Каждая строка описывает одну из N инструкций
Формат выходных данных
* Строка 1: Общая часть, покрашенная как минимум K слоями краски.
Примечание
6 единиц покрыто как минимум 2 слоями краски. Это интервалы: [-11,-8], [-4,-3], [0,2].

Сортировка событий

—Войти и решать

Islands#89852

Когда идут ливневые дожди, поля Фермера Джона всегда подтапливаются. И, поскольку имеется рельеф местности, в результате образуются острова, разделенные пространствами воды.
Поля ФД описаны как одноместный рельеф, указанием N (1 <= N <= 100,000) последовательных высот H(1)...H(n). Представим себе, что этот рельеф ограничен с обоих сторон валами бесконечной высоты. Теперь рассмотрим, что случится во время ливневого дождя: сначала водой покрываются нижние регионы, при этом получаются, разъединенные «острова», которые, в конце концов, могут все покрыться водой, если она будет прибывать и прибывать. Если уровень воды становится равным уровню куска земли, то этот кусок считается покрытым водой.

Пример показан на рисунке выше: слева мы добавили 1 единицу воды, и покрыли 4 острова. Затем мы добавили еще 7 единиц воды и теперь только два острова торчат из воды. Вычислите максимальное количество островов, которое мы сможем увидеть, если вода будет прибывать с нуля и до тех пор, пока весь рельеф не скроется под водой.

PROBLEM NAME: islands
Формат входных данных
* Строка 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит высоту H(i). (1 <= H(i) <= 1,000,000,000)
Формат выходных данных
* Строка 1: Одно целое число, определяющее максимальное количество островов, которое получится в один момент времени во время проливного дождя.

Сортировка событий

—Войти и решать

Flowerpot#89839

Фермер Джон нуждается в Вашей помощи в организации поливки. Вам даны координаты N поливателей (1 <= N <= 100,000) на декартовой плоскости, где y представляет высоту поливателя. А x - его местоположение на прямой.

Каждая капля воды падает вертикально (по направлению к оси x) со скоростью 1 единица в секунду. Вы должны разместить клумбу (шириной W) с цветами так, чтобы разница во времени, когда первая капля упадет на клумбу и когда последняя капля упадет на клумбу была не менее некоторой величины D. Капля, которая попадает на границу клумбы, считается попавшей на клумбу.
Вам даны значения D, а также местоположения и высоты поливателей. Вычислите минимально возможную величину W.
PROBLEM NAME: fpot
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа N и D. (1 <= D <=1,000,000) * Строки 2..1+N: Строка i+1 содержит разделенные пробелом координаты (x,y) поливателя i, все величины в интервале 0...1,000,000.
Формат выходных данных
* Строка 1: Одно целое число, минимально-возможную ширину клумбы. Выведите -1, если невозможно построить клумбу, которая получала бы воду в течение не менее D единиц времени
Примечание
Клумба шириной 2 возможна, если разместить ее с x от 4 до 6. Тогда она будет получать капли с поливателей #1 и #3, втечение времени 10-3 = 7.

Бинарный поиск по ответу Сортировка событий

—Войти и решать

Есть n стульев...#49857

Влад наконец-то достиг позиции тимлида в команде, но теперь у него совсем нет времени на дорогу домой, и ему придется спать в офисе. К сожалению, не все IT-компании могут позволить себе просторный и удобный коворкинг, в котором можно подремать, поэтому Влад будет спать на офисных стульях.

В офисе есть \(n\) стульев, \(i\)-й из которых имеет высоту \(h_i\) и ширину \(w_i\). Влад планирует выбрать любой набор офисных стульев \([i_1, i_2, \ldots, i_k]\) и расположить в ряд, чтобы на них можно было лечь. Рост Влада равен \(H\), поэтому, чтобы он мог удобно лежать, необходимо, чтобы суммарная ширина выбранных стульев была не меньше \(H\), то есть \[\sum\limits_{j=1}^k w_{i_j} \ge H \text{.}\]

Очевидно, что спать на стульях разной высоты неудобно. Назовем неудобностью выбранного набора максимальную разность высот двух соседних стульев в ряду, то есть \(\max\limits_{j=2}^k |h_{i_j} - h_{i_{j-1}}|\). Если набор состоит из одного стула, его неудобность равна \(0\).

Помогите Владу выбрать набор стульев так, чтобы на ряду из них можно было лежать, а неудобность этого ряда была как можно меньше.

Формат входных данных
В первой строке ввода через пробел даны два целых числа \(n\) и \(H\) — количество стульев и рост Влада (\(1 \le n \le 2 \cdot 10^5\); \(1 \le H \le 10^9\)).

Во второй строке ввода через пробел перечислены \(n\) целых чисел \(h_i\) — высоты стульев (\(1 \le h_i \le 10^9\)). В третьей строке в том же формате перечислены \(n\) целых чисел \(w_i\), равных ширине стульев (\(1 \le w_i \le 10^9\)).

Гарантируется, что \(H\) не превосходит суммы всех \(w_i\).

Формат выходных данных
Выведите единственное число — минимальное возможное неудобство среди всех подходящих наборов.

Замечание

В первом примере нужно выставить стулья \(2\) и \(4\) в любом порядке.

Во втором примере можно выбрать, например, следующие наборы: \([1, 5]\), \([2, 4, 3]\). Обратите внимание, что порядок стульев в наборе важен: неудобность набора \([2, 3, 4]\) равна \(\max(|5 - 3|, |4 - 5|) = \max(2, 1) = 2\), что больше, чем для набора \([2, 4, 3]\).

Бинарный поиск по ответу Использование сортировки Сортировка событий

✓ 31✗ 70300лёгкаяВойти и решать

Тестирование мессенджера - 2#49030

Перед выпуском VK Messenger’а разработчики из компании IT-компании <<VK>>, как и положено, убеждаются в корректности работы приложения. Проверкой корректности работы систем занимаются тестировщики и QA-инженеры.

Часть функциональных тестов для тестирования смены ников выглядит следующим образом:

генерируется случайный сценарий взаимодействия пользователей с приложением;
в приложении симулируется выполнение этого сценария;
проверяется корректность итогового состояния приложения.

Вам предлагается почувствовать себя в роли тестировщика и реализовать решение, обрабатывающее сценарий без взаимодействия с приложением. Результат обработки сценария затем будет сравниваться с итоговым состоянием приложения.

Каждый сценарий состоит из трех наборов событий.

Первый набор состоит из событий вида <<в момент времени \(t_i\) поступил запрос регистрации нового пользователя с ID \(\mathtt{id}_i\) и ником \(\mathtt{handle}_i\)>>.

Гарантируется, что ID уникальны для всех пользователей приложения. Если выбранный ник никем не занят, регистрация проходит успешно, иначе запрос на регистрацию отклоняется. Во втором случае пользователь с тем же ID может попробовать зарегистрироваться еще раз.
Второй набор описывает события вида <<в момент времени \(t_i\) пользователь с ником \(\mathtt{handle}_{i,1}\) отправляет запрос на смену ника на \(\mathtt{handle}_{i,2}\)>>.

Гарантируется, что для каждого такого запроса ник \(\mathtt{handle}_{i,1}\) кому-то принадлежит. Если \(\mathtt{handle}_{i,2}\) уже занят каким-либо пользователем, запрос отклоняется, иначе пользователь успешно меняет ник. При успешной смене ника старый ник перестает ассоциироваться с каким-либо пользователем, пока кто-то снова его не займет.
Третий набор описывает события вида <<в момент времени \(t_i\) пользователь с ником \(\mathtt{handle}_{i,1}\) отправляет сообщение пользователю с ником \(\mathtt{handle}_{i,2}\).

Гарантируется, что и \(\mathtt{handle}_{i,1}\) и \(\mathtt{handle}_{i,2}\) на момент времени \(t_i\) соответствуют каким-то зарегистрированным пользователям.

Также гарантируется, что никакие два события не происоходят в одно и то же время, то есть все \(t_i\) уникальны.

Вам даны описания всех трех наборов событий. Определите для каждого пользователя, сколько он всего получил сообщений, и от какого пользователя он получил больше всего сообщений за весь сценарий.

Формат входных данных
В первой строке ввода дано единственное целое число \(T\) — количество сценариев, которое вам необходимо обработать (\(1 \le T \le 100\)).

Далее следуют \(T\) описаний сценариев. Описание каждого сценария начинается с пустой строки, после чего следуют три набора событий. В первой строке описания \(q\)-го набора (\(q\) от \(1\) до \(3\)) дано единственное целое число \(n_q\) — количество событий в наборе, после чего следуют \(n_q\) строк в указанном ниже формате (\(1 \le n_1 + n_2 + n_3 \le 1000\); \(0 \le n_q\)).

События первого набора задаются в формате <<REG \(\mathtt{id}_i\) BY \(\mathtt{handle}_i\) AT \(t_i\)>>.
События второго набора задаются в формате <<CHANGE \(\mathtt{handle}_{i,1}\) TO \(\mathtt{handle}_{i,2}\) AT \(t_i\)>>.
События третьего набора задаются в формате <<SEND FROM \(\mathtt{handle}_{i,1}\) TO \(\mathtt{handle}_{i,2}\) AT \(t_i\)>>.

Моменты событий \(t_i\) — целые числа от \(1\) до \(10^9\). Также все \(\mathtt{id}_i\) — целые числа от \(1\) до \(10^9\), а \(\mathtt{handle}_i\) — строки из маленьких латинских букв длины не более \(10\).

Гарантируется, что в каждом наборе входных данных все \(t_i\) различны. Гарантируется, что успешно зарегистрированный пользователь не предпринимает попытки зарегистрироваться еще раз.

Формат выходных данных
Для каждого сценария выведите требуемую статистику для каждого пользователя.

В первой строке статистики выведите целое число \(q\) — количество зарегистрированных пользователей. В следующих \(q\) строках выведите статистику для каждого пользователя в порядке возрастания их ID в формате <<<\(\mathtt{id}\)> RECEIVED <\(\mathtt{total}\)> TOP <\(\mathtt{count}_\mathrm{top}\)> FROM <\(\mathtt{id}_\mathrm{top}\)>>>, где \(\mathrm{total}\) — суммарное количество полученных пользователем сообщений, \(\mathtt{id}_\mathrm{top}\) — ID пользователя, от которого он получил больше всего сообщений, а \(\mathtt{count}_\mathrm{top}\) — само количество сообщений, полученных от пользователя \(\mathtt{id}_\mathrm{top}\).

Если у некоторого пользователя есть несколько собеседников, отправивших ему максимальное число сообщений, выведите в качестве \(\mathtt{id}_\mathrm{top}\) минимальный из их ID. Если пользователь не получал сообщения, считайте \(\mathtt{count}_\mathrm{top}\) равным \(0\).

Задача на реализацию Сортировка событий Хеш

✓ 1✗ 2—Войти и решать

Тестирование мессенджера#49029

Часть функциональных тестов для тестирования смены ников выглядит следующим образом:

генерируется случайный сценарий взаимодействия пользователей с приложением;
в приложении симулируется выполнение этого сценария;
проверяется корректность итогового состояния приложения.

Каждый сценарий состоит из трех наборов событий.

Первый набор состоит из событий вида <<в момент времени \(t_i\) поступил запрос регистрации нового пользователя с ID \(\mathtt{id}_i\) и ником \(\mathtt{handle}_i\)>>.

Гарантируется, что ID уникальны для всех пользователей приложения. Если выбранный ник никем не занят, регистрация проходит успешно, иначе запрос на регистрацию отклоняется. Во втором случае пользователь с тем же ID может попробовать зарегистрироваться еще раз.
Второй набор описывает события вида <<в момент времени \(t_i\) пользователь с ником \(\mathtt{handle}_{i,1}\) отправляет запрос на смену ника на \(\mathtt{handle}_{i,2}\)>>.

Гарантируется, что для каждого такого запроса ник \(\mathtt{handle}_{i,1}\) кому-то принадлежит. Если \(\mathtt{handle}_{i,2}\) уже занят каким-либо пользователем, запрос отклоняется, иначе пользователь успешно меняет ник. При успешной смене ника старый ник перестает ассоциироваться с каким-либо пользователем, пока кто-то снова его не займет.
Третий набор описывает события вида <<в момент времени \(t_i\) пользователь с ником \(\mathtt{handle}_{i,1}\) отправляет сообщение пользователю с ником \(\mathtt{handle}_{i,2}\).

Гарантируется, что и \(\mathtt{handle}_{i,1}\) и \(\mathtt{handle}_{i,2}\) на момент времени \(t_i\) соответствуют каким-то зарегистрированным пользователям.

Также гарантируется, что никакие два события не происоходят в одно и то же время, то есть все \(t_i\) уникальны.

Вам даны описания всех трех наборов событий. Определите для каждого пользователя, сколько он всего отправил сообщений, и какому пользователю он отправил больше всего сообщений за весь сценарий.

Формат входных данных

В первой строке ввода дано единственное целое число \(T\) — количество сценариев, которое вам необходимо обработать (\(1 \le T \le 100\)).

События первого набора задаются в формате <<\(t_i\): REG \(\mathtt{id}_i\) \(\mathtt{handle}_i\)>>.
События второго набора задаются в формате <<\(t_i\): CHANGE \(\mathtt{handle}_{i,1}\) \(\mathtt{handle}_{i,2}\)>>.
События третьего набора задаются в формате <<\(t_i\): SEND \(\mathtt{handle}_{i,1}\) \(\mathtt{handle}_{i,2}\)>>.

Формат выходных данных
Для каждого сценария выведите требуемую статистику для каждого пользователя.

В первой строке статистики выведите целое число \(q\) — количество зарегистрированных пользователей. В следующих \(q\) строках выведите статистику для каждого пользователя в порядке возрастания их ID в формате <<<\(\mathtt{id}\)> SENT <\(\mathtt{total}\)> TOP <\(\mathtt{count}_\mathrm{top}\)> TO <\(\mathtt{id}_\mathrm{top}\)>>>, где \(\mathrm{total}\) — суммарное количество отправленных пользователем сообщений, \(\mathtt{id}_\mathrm{top}\) — ID пользователя, получившего от него больше всего сообщений, а \(\mathtt{count}_\mathrm{top}\) — само количество сообщений, отправленных пользователю \(\mathtt{id}_\mathrm{top}\).

Если у некоторого пользователя есть несколько собеседников, получивших от него максимальное число сообщений, выведите в качестве \(\mathtt{id}_\mathrm{top}\) минимальный из их ID. Если пользователь не отправлял сообщения, считайте \(\mathtt{count}_\mathrm{top}\) равным \(0\).

реализация Сортировка событий Хеш

✓ 1✗ 2—Войти и решать

Парковка#49011

Специально для \(n\) сотрудников ИТМО, пользующихся личными автомобилями, планируется открыть парковку. На парковке должно быть ровно \(n\) парковочных мест, каждому сотруднику должно достаться свое место.

Для экономии мест парковка будет разбита на несколько <<рядов>>. Места в каждом ряду нумеруются от \(1\) (самое дальнее от въезда) до длины ряда (самое ближнее ко въезду), и дальние места недоступны, пока не освободятся все более ближние.

Для каждого сотрудника известно, в какое время он приезжает, и в какое время заканчивает работу. Так как сотрудники ИТМО — очень трудолюбивые люди, каждый из них приезжает на работу в один день, а уезжает уже в следующий. Для каждого известно время, в которое он приезжает на работу \(t^\mathrm{in}_i\), и время, в которое он уезжает на следующий день \(t^\mathrm{out}_i\). Требуется назначить места сотрудникам так, чтобы никому из них не понадобилось ждать

появления доступного парковочного места, когда он приезжает;
возможности выехать, когда он заканчивает работу.

Более формально, если сотрудникам \(i\) и \(j\) назначены места \(p_i\) и \(p_j\) в одном ряду, и \(p_i < p_j\), должно выполняться \(t^\mathrm{in}_i < t^\mathrm{in}_j\) и \(t^\mathrm{out}_i > t^\mathrm{out}_j\).

Определите, какое минимальное число рядов понадобится, чтобы можно было распределить всех сотрудников по местам на парковке указанным образом, и найдите соответствующее распределение сотрудников по местам.

Формат входных данных

В первой строке ввода дано единственное целое число \(T\) — количество наборов входных данных (\(1 \le T \le 100\)). Далее следуют описания наборов входных данных.

В первой строке описания набора входных данных дано единственное целое число \(n\) — количество сотрудников, которых необходимо разместить на парковке.

Гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(10^5\).

Во второй строке набора входных данных через пробел перечислены \(n\) целых чисел \(t^\mathrm{in}_i\) — времена приезда сотрудников на работу (\(1 \le t^\mathrm{in}_i \le 10^9\)). В третьей строке в том же формате перечислены \(n\) целых чисел \(t^\mathrm{out}_i\) — времена отъезда сотрудников (\(1 \le t^\mathrm{out}_i \le 10^9\)).

Формат выходных данных
Выведите ответ на задачу для каждого набора входных данных в том порядке, в котором они перечислены во вводе.

В первой строке ответа выведите единственное целое число \(k\) — минимальное необходимое количество рядов. В \(i\)-й из следующих \(k\) строк выведите описание \(i\)-го ряда: первое число в строке \(\mathrm{cnt}_i\) должно быть равно количеству мест в ряду, после чего должны следовать \(\mathrm{cnt}_i\) целых чисел от \(1\) до \(n\) — номера сотрудников, занимающих места этого ряда, в порядке от самого глубокого к самому ближнему ко въезду.

Если существует несколько различных ответов, минимизирующих \(k\), выведите любой из них.

Использование сортировки Сортировка событий

✓ 4✗ 121 100средняяВойти и решать

Гости#38678

Вася переехал из своего родного города и очень скучает по старым друзьям. К сожалению, Вася снимает маленькую квартиру и одновременно в гости к нему может приехать только один друг. Каждый друг сказал Васе два числа A и B - с какого по какой день он может приехать в гости.
Каждый друг приезжает и уезжает в полдень. Каждый друг может приехать к Васе только один раз и остаться у него на несколько дней. Вася хотел бы, чтобы суммарное количество дней, когда у него в гостях есть кто-нибудь из друзей, было максимальным. Помогите ему определить даты приезда для каждого из друзей так, чтобы они не пересекались (допустима ситуация, что в один день один из друзей уезжает, а другой - уезжает) и суммарное время, когда у Васи в гостях есть кто-то из друзей, было максимальным.

Формат входных данных
В первой строке записаны целое число N (1 ≤ N ≤ 100000) - количество друзей Васи. В следующих N строках записано по два целых числа A_i и B_i (оба числа от 1 до 10⁹) - возможное время приезда i-го друга.

Формат выходных данных
Выведите N пар чисел L_i и R_i - номера дней, в которые приедет и уедет i-й друг соответственно (A_i ≤ L_i ≤ R_i ≤ B_i). Если i-го друга приглашать не нужно, выведите пару чисел -1 -1. Если правильных ответов несколько - выведите любой из них.

Примеры

№	Входные данные	Выходные данные
1	3 1 2 2 4 3 5	1 2 3 4 5 5
2	3 2 3 1 4 3 5	-1 -1 1 4 5 5

Жадный алгоритм Сортировка событий

✓ 10✗ 24700средняяВойти и решать

Межпланетные электрички#38381

На планете Кирнес есть железнодорожный вокзал, с которого проложен железнодорожный путь до Сириуса. Этот путь активно используется товарными поездами, ходящими по одному и тому же ежедневному расписанию с одинаковой скоростью. К началу туристического сезона было решено
запустить межпланетные электрички, следующие от вокзала до Сириуса. Электрички ходят по особому расписанию, которое надо согласовать с товарными поездами, поскольку железнодорожный путь является одноколейным.

Каждый день на планете Кирнес состоит из h часов. Каждый час состоит из m минут, причём m обязательно чётное. Известно, что на данный момент n товарных поездов отправляются с вокзала ежедневно по разу в день: i-й поезд отправляется в h_i часов и m_i минут.

Поскольку между Кирнесом и Сириусом активный пассажиропоток, то было решено пустить ровно по 2 электрички каждый час. Более того, по всем транспортным нормам необходимо, чтобы промежутки времени между отправлением электричек были равны \( {m \over 2}\)минутам. То есть для любой электрички предыдущая должна была отправиться ровно за \({m \over 2}\) минут до неё, а следующая должна отправиться ровно через \({m \over 2}\) минут после. Кроме этого, электричку надо подать на платформу за k минут до отправки. Пока электричка стоит на платформе, с неё не могут отправляться товарные поезда. При этом разрешается подавать электричку на платформу в ту же самую минуту, когда с неё отправляется предыдущий товарный поезд. А также поезда отправляются настолько быстро, что разрешено отправить электричку и следующий за ней товарный поезд в одну и ту же минуту.

Поскольку электрички отправляются каждый день с интервалом в \({m \over 2}\) минут, то первая электричка отправится с вокзала в 0 часов и t минут, причем t < \({m \over 2}\) . Обратите внимание, что если t < k, то платформа вокзала будет занята и последние k − t минут предыдущего дня.

Разумеется, не всегда можно составить корректное расписание электричек вместе со всеми товарными поездами. Тогда необходимо отменить некоторые товарные поезда, чтобы появилась возможность пустить электрички с соблюдением всех транспортных норм. При этом, чтобы грузоперевозчики не несли большие убытки, требуется отменить как можно меньше товарных поездов.

Составление такого расписания оказалось трудной задачей для правительства планеты, поэтому это было поручено вам. Найдите такое время t для запуска первой электрички, чтобы количество товарных поездов, которые потребуется отменить, было минимальным.

Формат входных данных
Первая строка содержит четыре целых числа n, h, m, k (1 ≤ n ≤ 100 000, 1 ≤ h ≤ 10⁹, 2 ≤ m ≤ 10⁹, 1 ≤ k ≤ \({m \over 2}\)) — число товарных поездов, количество часов и минут на планете Кирнес, а также время, которое электричка стоит у платформы. Гарантируется, что число минут m четное.
В следующих n строках вводится по два целых числа hi и mi (0 ≤ h_i < h, 0 ≤ m_i < m) — время отправления i-го поезда, часы и минуты соответственно. Гарантируется, что все товарные поезда отправляются в разное время.

Формат выходных данных
Выведите два числа: минимальное количество отмененных товарных поездов и t — время запуска первой за день электрички в минутах.
Во второй строке через пробел выведите номера отменяемых товарных поездов.

Примеры

№	Входные данные	Выходные данные
1	2 24 60 15 16 0 17 15	0 0
2	2 24 60 16 16 0 17 15	1 0 2

Замечание

В первом примере первую электричку надо отправить в 0:00. Тогда поезд в 16:00 отправится сразу после электрички, а электричку в 17:30 надо будет подать на платформу сразу после отправления товарного поезда в 17:15.
Во втором примере подать электричку на платформу надо за 16 минут до отправления. Сделать это без отмены какого-то товарного поезда не получится: если отправлять электричку в t ∈ [1, 15], то в 16:00 электричка уже должна быть на платформе, а с нее в это время отправляется первый товарный поезд. Если t ∈ {0, [16, 29]}, то второй товарный поезд в 17:15 не сможет уехать с платформы, потому что на ней уже будет стоять следующая электричка.
Если отменить второй поезд, то можно выбрать t = 0, тогда поезда будут отправляться в 0 и 30 минут каждый час, а столкновения с первым товарным поездом не будет. Также можно отменить только первый поезд и выбрать, например, t = 13.

реализация Сортировка событий

✓ 2✗ 391 200средняяВойти и решать

Городские центральные диаметры#37694

В одном большом городе готовятся к открытию новой ветки наземного метро. Она пролегает между двумя городами в пригороде по разные стороны от самого города, но проходя через него насквозь. Такую модель наземного метро назвали Городские центральные диаметры (ГЦД).

В рамках подготовки к запуску ГЦД было разработано специальное расписание, содержащее n рейсов в одном направлении и m рейсов в обратном. Для каждого рейса определены a_i - время отправления с первой конечной станции и b_i - время прибытия на вторую конечную станцию, для обратных рейсов c_j - время отправления со второй станции и d_j - время прибытия на первую станцию. Времена измеряются в минутах от начала дня. Внутри большого города поезда могут
передвигаться по различным маршрутам, поэтому поезд, отправившийся позже какого-то другого поезда, может прибыть раньше него.

Проекты такого масштаба ещё не запускались, а значит, будут происходить непредвиденные события и поезда будут задерживаться. Аналитики компании, обслуживающей ГЦД, посчитали, что при любых обстоятельствах поезд может опоздать на конечную станцию не более чем на t минут. Поезд может отправиться выполнять следующий рейс сразу же, как только закончил предыдущий.

Компании поручено во что бы то ни стало обеспечить выполнение каждого рейса. Определите, какое минимальное количество поездов необходимо иметь, чтобы ни один рейс гарантированно не был отменён даже в случае возможных задержек всех поездов. Поезда обязаны отправляться от
начальных станций строго по расписанию.
В начале и в конце дня поезда могут находиться на любой из станций. Перемещаться между станциями во время дня, кроме как по данному расписанию, поезда не могут.

Формат входных данных
Первая строка входных данных содержит максимальное время задержки при выполнении рейса t, 0 <= t <= 10⁹.
Следующая строка содержит число n - количество рейсов в расписании в одну сторону, 0 <= n <= 100. Следующие 2n строк содержат числа a₁, b₁, a₂, b₂, ..., a_n, b_n - время отправления поездов от первой станции и время их прибытия на вторую станцию, 0 <= a_i < b_i <= 10⁹.
Следующая строка содержит число m - количество поездов в расписании в обратную сторону, 0 <= m <= 100. Следующие 2m строк содержат время отправления c_j и прибытия d_j поездов в обратном направлении в аналогичном формате, 0 <= cj < dj <= 10⁹.
Поезда в расписании перечислены в произвольном порядке, не обязательно в порядке возрастания времени.

Формат выходных данных
Программа должна вывести одно целое число - минимальное количество поездов, необходимое для выполнения данного расписания.

Ввод	Вывод
4 2 3 8 5 10 1 11 15	3
1 2 15 18 7 9 2 11 14 1 3	1

Сортировка событий Теория расписаний

✓ 10✗ 211 000средняяВойти и решать

Лифт#33123

В современном многоэтажном офисе крупной компании установлен новый лифт. В

компании работает n сотрудников. Для проверки эффективности системы управления

лифтом требуется провести моделирование его работы в конце рабочего дня, когда все

сотрудники должны покинуть здание и спуститься на первый этаж.

В здании m этажей, пронумерованных от 1 до m снизу-вверх. Известно, что i-й

сотрудник подходит к лифту в секунду ti на этаже ai, чтобы спуститься на первый этаж.

На каждом этаже могут находиться люди, ожидающие лифт. Когда очередной

сотрудник подходит к лифту, он вызывает лифт, если на этом этаже лифт еще не вызван,

либо присоединяется к ожидающим лифт. Таким образом, помимо вызвавшего лифт, вместе

с ним лифт могут ожидать и другие сотрудники.

В каждый момент времени не более одного вызова является активным.

Изначально лифт свободен и находится на первом этаже. Когда поступает первый

вызов, этот вызов становится активным и лифт отправляется на соответствующий этаж. Если

несколько вызовов поступает одновременно, активным становится вызов от сотрудника с

меньшим номером.

Лифт перемещается между этажами со скоростью один этаж в секунду. Когда лифт

оказывается на этаже, откуда был сделан активный вызов, в него заходят все, кто уже

ожидает лифт на этом этаже, и лифт отправляется вниз на первый этаж, со скоростью один

этаж в секунду.

При движении вниз лифт останавливается на тех этажах, в которых был сделан вызов

на момент проезда лифта мимо этого этажа. Все ожидающие лифт сотрудники заходят в него

и вызов на этом этаже сбрасывается. Когда лифт завершает движение на первом этаже, все

люди выходят из лифта, а лифт ожидает следующего вызова.

Если в момент, когда лифт освободился, есть хотя бы один необслуженный вызов,

активируется вызов, который поступил раньше других. Если несколько вызовов поступило

одновременно, активируется вызов от сотрудника с меньшим номером. Лифт продолжает

обслуживание описанным образом, пока все n сотрудников не окажутся на первом этаже.

Будем считать, что люди входят и выходят из лифта мгновенно. Каждую секунду

сначала люди подходят и вызывают лифт, а затем выполняются соответствующие действия

(лифт перемещается на соседний этаж, в него входят или из него выходят люди, принимается

решение, на какой вызов лифт должен отреагировать).

Требуется написать программу, которая по описанию вызовов лифта для каждого

сотрудника определяет, в какой момент этот сотрудник окажется на первом этаже.

Формат входных данных

Первая строка входных данных содержит целые числа n и m — количество людей,

вызывающих лифт, и количество этажей в здании (1 ≤ n ≤ 10⁵, 2 ≤ m ≤ 10⁹).

Следующие n строк описывают сотрудников, i-я из этих строк содержит два целых

числа ti и ai — секунду, в которую i-й сотрудник подходит к лифту, и номер этажа, на

котором это происходит (1 ≤ t1 ≤ t2 ≤ … ≤ tn ≤ 10⁹, 2 ≤ ai ≤ m)

Формат выходных данных

Выходные данные должны содержать n целых чисел, для каждого сотрудника

требуется вывести секунду, в которую он выйдет из лифта на первом этаже.

Ввод	Вывод
5 4 2 3 2 4 5 2 5 3 9 3	6 12 6 12 12

Пояснение к примеру

Пример работы лифта по шагам показан в следующей таблице.

Использованные в пояснении к примеру обозначения

Использование сортировки Множества Сортировка событий Структуры данных

✓ 0✗ 91 300средняяВойти и решать