A: Закрашенная часть прямой

На числовой прямой окрасили $N$ отрезков. Известны координаты левого и правого концов каждого отрезка ($L_i$ и $R_i$). Найти длину окрашенной части числовой прямой.
В первой строке записано число $N$, в следующих $N$ строках — пары целых чисел $L_i$ и $R_i$ ($-10^9 \leqslant L_i \leqslant R_i \leqslant 10^9, 1 \leqslant N \leqslant 15 000$).
Программа должна вывести одно число — длину окрашенной части прямой.

B: Межрегиональная олимпиада (простой вариант)

На межрегиональной олимпиаде по программированию роботов соревнования проводятся в один тур и в необычном формате. Задачи участникам раздаются последовательно, а не все в самом начале тура, и каждая $i$-я задача ($1 \leqslant i \leqslant n$) становится доступной участникам в свой момент времени $s_i$.
При поступлении очередной задачи каждый участник должен сразу определить, будет он ее решать или нет. В случае, если он выбирает для решения эту задачу, то у него есть $t_i$ минут на то, чтобы сдать её решение на проверку, причем в течение этого времени он не может переключиться на решение другой задачи. Если же участник отказывается от решения этой задачи, то в будущем он не может к ней вернуться. В тот момент, когда закончилось время, отведённое на задачу, которую решает участник, он может начать решать другую задачу, ставшую доступной в этот же момент, если такая задача есть, или ждать появления другой задачи. При этом за правильное решение $i$-й задачи участник получает $c_i$ баллов (внимание — в данной задаче все $c_i$ одинаковы).
Петя понимает, что важную роль на такой олимпиаде играет не только умение решать задачи, но и правильный стратегический расчет того, какие задачи надо решать, а какие пропустить. Ему, как и всем участникам, до начала тура известно, в какой момент времени каждая задача станет доступной, сколько времени будет отведено на ее решение и сколько баллов можно получить за ее решение. Петя может успешно решить за отведённое время и сдать на проверку любую задачу, которую он выберет для решения на олимпиаде.
Требуется написать программу, которая определяет, какое максимальное количество баллов Петя сможет получить при оптимальном выборе задач, которые он будет решать, а также количество и перечень таких задач.
Первая строка входного файла содержит одно целое число $n$ ($1 \leqslant n \leqslant 10^5$) количество задач на олимпиаде.
Последующие $n$ строк содержат описания задач, по три числа на каждой строке: $s_i$ момент появления $i$-й задачи в минутах, $t_i$ время, отведённое на её решение в минутах, и $c_i$ сколько баллов получит участник за решение этой задачи ($1 \leqslant s_i, t_i, c_i \leqslant 10^9$).
Первая строка выходного файл должна содержать одно число — максимальное количество баллов, которое сможет получить Петя на олимпиаде.
Вторая строка должна содержать одно целое число $m$ — количество задач, которые надо решить при оптимальном выборе.
Третья строка должна содержать $m$ разделённых пробелом целых чисел — номера этих задач в порядке их решения. Задачи пронумерованы, начиная с единицы, в порядке их описания во входном файле.
Если оптимальных ответов несколько, необходимо вывести любой из них.

C: Кассы

На одном из московских вокзалов билеты продают $N$ касс. Каждая касса работает без перерыва определённый промежуток времени по фиксированному расписанию (одному и тому же каждый день). Требуется определить, на протяжении какого времени в течение суток работают все кассы одновременно.
В первой строке вводится одно целое число $N$ ($0 < N\leqslant10000$).
В каждой из следующих $N$ строк через пробел расположены $6$ целых чисел, первые три из которых обозначают время открытия кассы в часах, минутах и секундах (часы — целое число от $0$ до $23$, минуты и секунды — целые числа от $0$ до $59$), оставшиеся три — время закрытия в том же формате. Числа разделены пробелами.
Время открытия означает, что в соответствующую ему секунду касса уже работает, а время закрытия — что в соответствующую секунду касса уже не работает. Например, касса, открытая с $10$ ч $30$ мин $30$ с до $10$ ч $35$ мин $30$ с, ежесуточно работает $300$ секунд.
Если время открытия совпадает с временем закрытия, то касса работает круглосуточно. Если первое время больше второго, то касса начинает работу до полуночи, а заканчивает — на следующий день.
Требуется вывести одно число — суммарное время за сутки (в секундах), на протяжении которого работают все $N$ касс.

D: Отрезки на прямой

Имеется (большой) отрезок длины $L$. На нём разложено $N$ (маленьких) отрезков так, что никакой маленький отрезок не вылезает за границы большого отрезка. Требуется измерить толщину покрытия большого отрезка маленькими в $M$ точках.
Во входном файле даны сначала $L, N, M$ ($1 \leqslant L \leqslant 10000, 1 \leqslant N \leqslant 10000, 1 \leqslant M \leqslant 100000$).
Далее записаны $N$ пар чисел $l \leqslant r$ от $1$ до $L$ — левые и правые концы маленьких отрезков.
Затем записаны $M$ чисел от $1$ до $L$ — интересующие нас точки. Все числа целые.
Выведите $M$ чисел — толщину покрытия отрезками в каждой точке.

E: Минимальное покрытие

На прямой задано некоторое множество отрезков с целочисленными координатами концов $[L_i, R_i]$. Выберите среди данного множества подмножество отрезков, целиком покрывающее отрезок $[0, M]$, ($M$ — натуральное число), содержащее наименьшее число отрезков.
В первой строке указана константа $M$ ($1\leqslant M\leqslant5000$). В каждой последующей строке записана пара чисел $L_i$ и $R_i$ ($|L_i|,|R_i|\leqslant50000$), задающая координаты левого и правого концов отрезков. Список завершается парой нулей. Общее число отрезков не превышает $10^5$.
В первой строке выходного файла выведите минимальное число отрезков, необходимое для покрытия отрезка $[0; M]$. Далее выведите список покрывающего подмножества, упорядоченный по возрастанию координат левых концов отрезков. Список отрезков выводится в том же формате, что и во входe. Завершающие два нуля выводить не нужно.
Если покрытие отрезка $[0, M]$ исходным множеством отрезков $[L_i, R_i]$ невозможно, то следует вывести единственную фразу No solution.

F: Древние цивилизации

Петя нашел в энциклопедии даты рождения и гибели N различных древних цивилизаций и теперь хочет узнать о влиянии культуры одних цивилизаций на культуру других.
Петя предположил, что между цивилизациями A и B происходил культурный обмен, если они сосуществовали в течение некоторого ненулевого промежутка времени. Например, если цивилизация A зародилась в 600 году до н.э. и существовала до 400 года до н.э., а цивилизация B зародилась в 450 году до н.э. и существовала до 300 года до н.э., то культура каждой из этих цивилизаций оказывала влияние на развитие другой цивилизации в течение 50 лет. В то же время, если цивилизация C зародилась в 400 году до н.э. и существовала до 50 года до н.э., то она не смогла осуществить культурного обмена с цивилизацией A, в то время как культурный обмен с цивилизацией B продолжался в течение 100 лет.
Теперь для выполнения своих исследований Петя хочет найти такую пару цивилизаций, культурный обмен между которыми имел место на протяжении наименьшего ненулевого промежутка времени.
В первой строке вводится число $N$ — количество цивилизаций, культура которых интересует Петю ($1\leqslant N \leqslant 10^5$). Следующие $N$ строк содержат описание цивилизаций — в каждой строке задаются два целых числа $S_i$ и $E_i$ — год зарождения и год гибели соответствующей цивилизации. Все числа не превосходят $10^9$ по абсолютной величине, $S_i < E_i$.
Выведите два числа — номера цивилизаций, периоды существования которых имеют наименьшее ненулевое пересечение. Если никакие две цивилизации не пересекаются во времени, выведите единственное число $0$.

G: Реклама

Фирма NNN решила транслировать свой рекламный ролик в супермаркете XXX. Однако денег, запланированных на рекламную кампанию, хватило лишь на две трансляции ролика в течение одного рабочего дня.
Фирма NNN собрала информацию о времени прихода и времени ухода каждого покупателя в некоторый день. Менеджер по рекламе предположил, что и на следующий день покупатели будут приходить и уходить ровно в те же моменты времени.
Помогите ему определить моменты времени, когда нужно включить трансляцию рекламных роликов, чтобы как можно большее количество покупателей прослушало ролик целиком от начала до конца хотя бы один раз. Ролик длится ровно 5 единиц времен. Трансляции роликов не должны пересекаться, то есть начало второй трансляции должно быть хотя бы на 5 единиц времени позже, чем начало первой.
Если трансляция ролика включается, например, в момент времени $10$, то покупатели, пришедшие в супермаркет в момент времени $10$ (или раньше) и уходящие из супермаркета в момент $15$ (или позднее) успеют его прослушать целиком, а, например, покупатель, пришедший в момент времени $11$, равно как и покупатель, уходящий в момент $144$ — не успеют. Если покупатель успевает услышать только конец первой трансляции ролика (не сначала) и начало второй трансляции (не до конца), то считается, что он не услышал объявления. Если покупатель успевает услышать обе трансляции ролика, то при подсчете числа людей, прослушавших ролик, он все равно учитывается всего один раз (фирме важно именно количество различных людей, услышавших ролик).
В первой строке входного файла вводится число $N$ — количество покупателей ($1\leqslant N\leqslant2000$). В следующих $N$ строках записано по паре натуральных чисел — время прихода и время ухода каждого из них. Все значения времени — натуральные числа, не превышающие $10^9$. Время ухода человека из супермаркета всегда строго больше времени его прихода в супермаркет.
Выведите через пробел три числа: количество покупателей, которые прослушают ролик целиком от начала до конца хотя бы один раз, и моменты времени, когда должна начинаться трансляция ролика. Моменты времени должны быть выведены в возрастающем порядке и должны быть натуральными числами, не превышающими $2\cdot10^9$. Если вариантов ответа несколько, выведите любой из них.

H: Снова отрезки на прямой

На прямой задано $N$ попарно различных отрезков $[a_i,b_i]$ ($i=1,2,\dots N,a_i < b_i$). Будем говорить, что отрезок номер $i$ непосредственно содержится в отрезке номер $j$ ($i\ne j$), если:

• он полностью принадлежит $j$-му отрезку (то есть $a_j\leqslant a_i$ и $b_i\leqslant b_j$),
• среди заданных $N$ отрезков не найдётся такого отрезка (с номером $k$), что $i$-й отрезок принадлежит $k$-му и $k$-й принадлежит $j$-му (здесь $i$, $j$ и $k$ — различные числа).

Ваша задача — для каждого из данных отрезков найти тот, в котором он непосредственно содержится, либо сообщить, что таких нет. Если данный отрезок непосредственно содержится сразу в нескольких — подходит любой из них.
Сначала вводится целое число $N$ ($1\leqslant N\leqslant10^5$). Далее идут $N$ пар целых чисел $a_i$, $b_i$ ($-10^9\leqslant a_i, b_i \leqslant 10^9$).
Выведите $N$ чисел. Число номер $i$ должно быть равно номеру отрезка, в котором непосредственно содержится отрезок номер $i$, либо $0$ — если такого не существует.
Если существует несколько решений, выведите любое.

I: Межрегиональная олимпиада (сложный вариант)

На межрегиональной олимпиаде по программированию роботов соревнования проводятся в один тур и в необычном формате. Задачи участникам раздаются последовательно, а не все в самом начале тура, и каждая $i$-я задача ($1 \leqslant i \leqslant n$) становится доступной участникам в свой момент времени $s_i$.
При поступлении очередной задачи каждый участник должен сразу определить, будет он ее решать или нет. В случае, если он выбирает для решения эту задачу, то у него есть $t_i$ минут на то, чтобы сдать её решение на проверку, причем в течение этого времени он не может переключиться на решение другой задачи. Если же участник отказывается от решения этой задачи, то в будущем он не может к ней вернуться. В тот момент, когда закончилось время, отведённое на задачу, которую решает участник, он может начать решать другую задачу, ставшую доступной в этот же момент, если такая задача есть, или ждать появления другой задачи. При этом за правильное решение $i$-й задачи участник получает $c_i$ баллов.
Петя понимает, что важную роль на такой олимпиаде играет не только умение решать задачи, но и правильный стратегический расчет того, какие задачи надо решать, а какие пропустить. Ему, как и всем участникам, до начала тура известно, в какой момент времени каждая задача станет доступной, сколько времени будет отведено на ее решение и сколько баллов можно получить за ее решение. Петя может успешно решить за отведённое время и сдать на проверку любую задачу, которую он выберет для решения на олимпиаде.
Требуется написать программу, которая определяет, какое максимальное количество баллов Петя сможет получить при оптимальном выборе задач, которые он будет решать, а также количество и перечень таких задач.
Первая строка входного файла содержит одно целое число $n$ ($1 \leqslant n \leqslant 10^5$) количество задач на олимпиаде.
Последующие $n$ строк содержат описания задач, по три числа на каждой строке: $s_i$ момент появления $i$-й задачи в минутах, $t_i$ время, отведённое на её решение в минутах, и $c_i$ сколько баллов получит участник за решение этой задачи ($1 \leqslant s_i, t_i, c_i \leqslant 10^9$).
Первая строка выходного файл должна содержать одно число — максимальное количество баллов, которое сможет получить Петя на олимпиаде.
Вторая строка должна содержать одно целое число $m$ — количество задач, которые надо решить при оптимальном выборе.
Третья строка должна содержать $m$ разделённых пробелом целых чисел — номера этих задач в порядке их решения. Задачи пронумерованы, начиная с единицы, в порядке их описания во входном файле.
Если оптимальных ответов несколько, необходимо вывести любой из них.

V: Покрытие отрезками

Даны $N$ отрезков на прямой и координаты $M$ точек. Для каждой из точек отрезка $[1,L]$ определите — каким количеством данных отрезков они покрываются?
Во входном файле даны сначала $L,N,M~(1\leqslant L\leqslant10000,1\leqslant N\leqslant10000,1\leqslant M\leqslant100000)$.
Далее идут $N$ пар чисел $l\leqslant r$ от $1$ до $L$ — левые и правые концы отрезков. Затем перечислены M чисел от $1$ до $L$.
Выведите $M$ чисел — количество отрезков, покрывающую каждую из указанных $M$ точек.

W: Закраска прямой

На числовой прямой окрасили $N$ отрезков. Известны координаты левого и правого концов каждого отрезка ($L_i$ и $R_i$). Найти длину окрашенной части числовой прямой.
В первой строке находится число $N$, в следующих $N$ строках — пары $L_i$ и $R_i$. $L_i$ и $R_i$ — целые, $-10^9\leqslant L_i\leqslant R_i\leqslant10^9,1\leqslant N\leqslant15 000$.
Вывести одно число — длину окрашенной части прямой.

X: Задача о минимальном покрытии

На прямой задано некоторое множество отрезков с целочисленными координатами концов $[L_i, R_i]$. Выберите среди данного множества подмножество отрезков, целиком покрывающее отрезок $[0, M]$, ($M$ — натуральное число), содержащее наименьшее число отрезков.
В первой строке указано число $M~(1\leqslant M\leqslant5000)$. В каждой последующей строке записана пара чисел $L_i$ и $R_i~(|L_i|,|R_i|\leqslant50000)$, задающая координаты левого и правого концов отрезков. Список завершается парой нулей. Общее число отрезков не превышает $100000$.
В первой строке выходного файла выведите минимальное число отрезков, необходимое для покрытия отрезка $[0,M]$. Далее выведите список покрывающего подмножества, упорядоченный по возрастанию координат левых концов отрезков. Список отрезков выводится в том же формате, что и во входe. Завершающие два нуля выводить не нужно. Если покрытие отрезка $[0,M]$ исходным множеством отрезков $[L_i,R_i$] невозможно, то следует вывести единственную фразу No solution.