Маршрутки Оша


Отправить решение Решать в редакторе

Сложность: 70%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Утром студенты ОшГУ разъезжаются по городу на маршрутках. Остановки Оша пронумерованы от 1 до n; остановка 1 находится у главного корпуса университета, а остановка n — у подножия Сулайман-Тоо, где сегодня проходит студенческий квест.

Известно расписание на весь день: m рейсов. Рейс i отправляется с остановки a[i] в момент s[i] и без промежуточных остановок прибывает на остановку b[i] в момент f[i] (s[i] < f[i]). Время измеряется в секундах от начала суток.

Чтобы пересесть, нужно время: выйдя из маршрутки на остановке v в момент T, студент может сесть в любой рейс, отправляющийся с v в момент не раньше T + c[v] (переход к другой стороне улицы, поиск нужной маршрутки). На остановке 1 в начале пути пересадки нет: если студент пришёл туда в момент t, он может сесть в любой рейс с отправлением не раньше t. Ждать на остановках можно сколько угодно, ходить пешком между остановками нельзя.

Поступает q вопросов: Бакыт приходит на остановку 1 в момент t. В какой самый ранний момент он может оказаться на остановке n?

Рисунок

Входные данные

В первой строке — два целых числа n и m (2 ≤ n ≤ 200 000, 1 ≤ m ≤ 300 000).

Во второй строке — n целых чисел c[1], …, c[n] (0 ≤ c[v] ≤ 10⁹) — время пересадки на каждой остановке.

В каждой из следующих m строк — четыре целых числа a[i], b[i], s[i], f[i] (1 ≤ a[i], b[i] ≤ n, a[i] ≠ b[i], 0 ≤ s[i] < f[i] ≤ 10⁹).

Далее — число q (1 ≤ q ≤ 200 000) и q строк, в каждой одно целое число t (0 ≤ t ≤ 10⁹).

Выходные данные

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

Пример 1

Вход:

4 6
0 5 2 0
1 2 0 10
1 3 5 12
2 4 14 20
3 4 13 30
2 4 16 18
1 4 25 40
4
0
5
6
26

Выход:

18
40
40
-1

Пояснение

Выйдя в момент 0, Бакыт едет рейсом 1 → 2 (прибытие в 10). На остановке 2 пересадка занимает 5 секунд, поэтому рейс в 14 он пропускает, а рейс в 16 успевает и прибывает в 18.

Выйдя в момент 5, он может уехать только рейсом 1 → 3 (прибытие в 12), но пересадка на остановке 3 занимает 2 секунды, и рейс в 13 уходит без него. Остаётся прямой рейс в 25 с прибытием в 40.

Система оценивания

Подзадача Баллы Дополнительные ограничения
1 20 n, m, q ≤ 1000
2 25 q ≤ 10
3 55 без дополнительных ограничений

Баллы за подзадачу начисляются, только если пройдены все её тесты.


Комментарии

Еще нет ни одного комментария.