--->
30 задач
<---
Источники
См. «Двоичная куча (пирамида). Пирамидальная сортировка. Приоритетная очередь» (PDF), стр. 13, задача 7.
Ограничение времени – 1 секунда
См. «Двоичная куча (пирамида). Пирамидальная сортировка. Приоритетная очередь» (PDF), стр. 13, задача 8.
Ограничение времени – 1 секунда
См. «Двоичная куча (пирамида). Пирамидальная сортировка. Приоритетная очередь» (PDF), стр. 14, задача 9.
Ограничение времени – 1 секунда
Васин жесткий диск состоит из \(M\) секторов. Вася последовательно устанавливал на него различные операционные системы следующим методом: он создавал новый раздел диска из последовательных секторов, начиная с сектора номер \(a_i\) и до сектора \(b_i\) включительно, и устанавливал на него очередную систему. При этом если очередной раздел хотя бы по одному сектору пересекается с каким-то ранее созданным разделом, то ранее созданный раздел «затирается», и операционная система, которая на него была установлена, больше не может быть загружена.
Напишите программу, которая по информации о том, какие разделы на диске создавал Вася, определит, сколько в итоге работающих операционных систем установлено и в настоящий момент работает на Васином компьютере.
Сначала вводятся натуральное число \(M\) — количество секторов на жестком диске (1 ≤ \(M\) ≤ \(10^9\)) и целое число \(N\) — количество разделов, которое последовательно создавал Вася (0 ≤ \(N\) ≤ 100 000).
Далее идут \(N\) пар чисел \(a_i\) и \(b_i\), задающих номера начального и конечного секторов раздела (1 ≤ \(a_i\) ≤ \(b_i\) ≤ \(M\)).
Выведите одно число — количество работающих операционных систем на Васином компьютере.
10 3 1 3 4 7 3 4
1
Мосгортранс в честь дня своего рождения решил провести соревнования, и, по аналогии с «Бегущим городом» назвать их «Ездящий город».
Участник соревнований получает маршрутный лист, где указано, какие контрольные пункты и в каком порядке он должен посетить (в каждом пункте участник должен отметиться). При этом участник должен отмечаться в пунктах строго в указанном порядке. Какие-то пункты может потребоваться посетить несколько раз.
Специально по случаю соревнования между контрольными пунктами будут ходить автобусы. Перемещаться от контрольного пункта к контрольному пункту разрешается только на автобусах. При этом можно пользоваться как прямым рейсом, соединяющим контрольные пункты (если он существует), так и добираться с пересадкой через другие контрольные пункты (если это оказывается быстрее или если прямого маршрута вовсе нет), при этом в пересадочных пунктах участник не отмечается.
Известен маршрутный лист участника и расписание движения автобусов. Требуется определить минимальное время, которое понадобится участнику на прохождение маршрута.
Сначала вводится число \(N\) — общее количество контрольных пунктов (2≤\(N\)≤10000).
Далее вводится количество автобусных маршрутов \(K\) (1≤\(K\)≤50000). Далее идет \(K\) описаний автобусных маршрутов.
Каждый маршрут описывается четырьмя числами \(A_i\), \(B_i\), \(C_i\), \(D_i\), которые означают, что каждые \(C_i\) минут (т.е. в моменты времени 0, \(C_i\), 2*\(C_i\), …) автобус выходит от контрольного пункта \(A_i\) и через \(D_i\) минут прибывает к контрольному пункту \(B_i\). Все \(C_i\) и \(D_i\) — натуральные и не превышают 10000.
Будем считать, что времени на то, чтобы отметиться на контрольном пункте и на то, чтобы пересесть с автобуса на автобус, участнику не требуется. Т.е. если, например, в момент 10 он прибывает на какой-то контрольный пункт, то дальше он может уехать любым автобусом, отправляющимся от этого контрольного пункта в момент времени 10 или позднее.
Далее вводится число \(M\) — количество контрольных пунктов в маршрутном листе участника (2≤\(M\)≤50). Далее вводятся \(M\) чисел \(P_1\), \(P_2\), …, \(P_M\) — номера контрольных пунктов, которые нужно посетить (числа в этом списке могут повторяться). В момент времени 0 участник находится в пункте \(P_1\). Временем прохождения маршрута считается момент времени, когда участник окажется в пункте \(P_M\).
Выведите одно число — минимальное время, за которое участник может пройти маршрут. Если существующие автобусные рейсы не позволяют пройти маршрут, выведите одно число –1 (минус один).
2 2 2 1 3 1 1 2 5 4 3 1 2 1
7
3 4 2 1 30 10 1 2 50 40 2 3 45 10 3 1 55 10 3 1 2 1
65
2 2 1 2 3 1 1 2 5 4 3 1 2 1
-1