1494: Діаметральне метро


Submit solution

Points: 35
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

В одному великому мiстi готуються до вiдкриття нової гiлки наземного метро. Вона пролягає мiж двома мiстами в передмiстi по рiзнi боки вiд самого мiста i проходить через нього наскрiзь. Таку модель наземного метро назвали Мiськi центральнi дiаметри (МЦД).

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

Всерединi великого мiста поїзди можуть пересуватися по рiзних маршрутах, тому поїзд, що вiдправився пiзнiше якогось iншого поїзда, може прибути ранiше за нього. Проекти такого масштабу ще не запускалися, а значить, будуть вiдбуватися непередбаченi подiї та поїзди будуть затримуватися. Аналiтики компанiї, яка обслуговує МЦД, порахували, що при будь-яких обставинах поїзд може запiзнитися на кiнцеву станцiю не бiльше нiж на \(t\) хвилин. Поїзд може вiдправитися виконувати наступний рейс вiдразу ж, як тiльки закiнчив попереднiй.

Компанiї доручено за будь-яку цiну забезпечити виконання кожного рейсу. Визначте, яку мiнiмальну кiлькiсть поїздiв необхiдно мати, щоб жоден рейс гарантовано не був скасований навiть в разi можливих затримок всiх поїздiв. Потяги зобов’язанi вирушати вiд початкових станцiй строго за розкладом. На початку i в кiнцi дня поїзди можуть перебувати на будь-якiй станцiї. Перемiщатися мiж станцiями пiд час дня, окрiм як за розкладом, потяги не можуть.

Формат вхідних даних

Перший рядок вхiдних даних мiстить максимальний час затримки при виконаннi рейсу \(t\), \(0 \le t \le 10^9\).

Наступний рядок мiстить число \(n\) - кiлькiсть рейсiв в розкладi в одну сторону, \(0 \le n \le 100\).

Наступнi \(2n\) рядкiв мiстять числа \(a_1 , b_1 , a_2 , b_2 , ..., a_n\) , \(b_n\) - час вiдправлення поїздiв вiд першої станцiї i час їх прибуття на другу станцiю, \(0 \le a_i < b_i \le 10^9\).

Наступний рядок мiстить число \(m\) - кiлькiсть поїздiв в розкладi в зворотному напрямку, \(0 \le m \le 100\).

Наступнi \(2m\) рядкiв мiстять час вiдправлення \(c_j\) i прибуття \(d_j\) поїздiв в зворотному напрямку в аналогiчному форматi, \(0 \le c_j < d_j \le 10^9\).

Потяги в розкладi розмiщенi в довiльному порядку, не обов’язково в порядку зростання часу.

Формат вихідних даних

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

Система оцiнки

Розв’язки, якi правильно працюють для випадку, коли значення \(t, a_i , b_i , c_j , d_j\) не перевищують 100, оцiнюватимуться в 40 балiв.

Розв’язки, якi правильно працюють для випадку, коли значення \(t, a_i , b_i , c_j , d_j\) не перевищують \(10^5\), оцiнюватимуться в 70 балiв.

Приклад вхідних даних

4
2
3
8
5
10
1
11
15

Приклад вихідних даних

3

Приклад вхідних даних

1
2
15
18
7
9
2
11
14
1
3

Приклад вихідних даних

1

Пояснення

У першому тестi \(t\) = 4 , n = 2 , m = 1. Перший поїзд їде в момент часу \(a_1\) = 3 i прибуває в \(b_1\) = 8. Другий поїзд вiдправляється в момент часу \(a_2\) = 5 i прибуває в \(b_2\) = 10. З другої станцiї до першої поїзд вiдправляється в \(c_1\) = 11 i прибуває в \(d_1\) = 15 . Перший поїзд не встигає виконати зворотний рейс, тому що вiн прибуває на другу станцiю за розкладом в 8, але може спiзнитися на 4 хвилини, тобто вiн зможе виконати зворотний рейс тiльки при вiдправленнi не ранiше 12 хвилини. Тому для реалiзацiї розкладу необхiдний третiй поїзд.

У другому тестi \(t = 1 , n = 2 , m = 2\). Поїзд по черзi виконує всi рейси. Спершу вiн виконує рейс вiд другої станцiї до першої - вiдправленням в \(c_2 = 1\), прибуттям в \(d_2 = 3\). Потiм рейс вiд першої станцiї до другої - вiдправленням \(a_2 = 7\), прибуттям \(b_2 = 9\). Далi виконує рейс вiд другої станцiї до першої - вiдправленням \(c_1 = 11\), прибуттям \(d_1 = 14 \). Нарештi, вiн виконує рейс вiд першої станцiї до другої - вiдправленням в \(a_1 = 15\), прибуттям в \(b_1 = 18\). Максимальний час затримки в дорозi дорiвнює 1, тому один потяг зможе виконати всi цi рейси.

Джерело: olympiads.ru


Comments


  • 0
    Hydra  commented on July 5, 2021, 3:12 p.m.

    Остання моя відправка в мене на ноутбуці дає на першому тесті відповідь 3, а під час тестування сервером 4. Що робити?)


    • -1
      zvit  commented on July 25, 2021, 3:57 p.m.

      важко відповісти, попробую повторити у себе...