Залізниця#10663
Між Цюрихом та Лугано пролягає залізниця довжиною кілометрів. Залізниця перетинає мальовничі Альпи, що призводить до вражаючих пейзажів під час їзди. Оскільки деякі перевали занадто високі для залізниці, на колії є тунелів. -й з них починається на відстані a_i кілометрів від Цюриха і закінчується на відстані b_i кілометрів від Цюриха. (Таким чином, довжина -го тунелю становить b_i - a_i.)
У вас є розклад залізничного сполучення між двома містами. Існує потягів з Цюриха в Лугано, -ий потяг відходить в c_j хвилин. А також потягів з Лугано в Цюрих, -ий потяг відправляється в d_k хвилин. Усі потяги, що курсують на колії, мають постійну швидкість 1 кілометр на хвилину, незалежно від їхнього напрямку та від того, перебувають вони в тунелі чи ні. На маршруті немає станцій, і потяги ніколи не зупиняються у семафорів. Отже, кожен потяг прибуває до місця призначення рівно за хвилин.
Довжина потяга незначна порівняно з довжиною залізниці, тому в цій задачі, будь ласка, припустіть, що кожен потяг — це точка, яка рухається вздовж залізниці.
Зазвичай залізниця має дві колії: по одній у кожному напрямку. Єдиним винятком є тунелі. Кожен тунель має лише одну колію, яку можна використовувати в будь-якому напрямку.
Кожного разу, коли два потяги, що їдуть у протилежних напрямках, стикаються за межами тунелю, вони можуть безпечно проїжджати один одного. Сюди входять потяги, які зустрічаються точно в кожному кінці тунелю. З іншого боку, якщо пара потягів зустрічається строго всередині тунелю, відбувається зіткнення.
Враховуючи опис тунелів та потягів, визначте, чи відбудеться зіткнення.
Перший рядок містить чотири цілі числа , , , (1 \leq s \leq 1\,000\,000\,000, 0 \leq t \leq 100\,000, 0 \leq m, n \leq 2\,000) — довжина залізниці, кількість тунелів, кількість потягів з Цюриха та кількість потягів з Лугано відповідно.
Другий рядок містить цілих чисел a_i (0 \leq a_i < s) — початкові позиції тунелів.
Третій рядок містить цілих чисел b_i (0 < b_i \leq s) — кінцеві позиції тунелів.
Для кожного від до , виконується умова a_i < b_i. А також для кожного від до t-1, виконується умова b_i < a_{i+1}. (Іншими словами, кожен тунель має додатню довжину, тунелі не перетинаються, тунелі дані у порядку зростання відстані від Цюриха.)
Четвертий рядок містить цілих чисел c_j (0 \leq c_j \leq 1\,000\,000\,000) — час початку (у хвилинах) потягів, що вирушають з Цюриха. Вони задані в порядку зростання, тобто c_j < c_{j+1} для всіх допустимих .
П'ятий рядок містить цілих чисел d_k (0 \leq d_k \leq 1\,000\,000\,000) — час початку (у хвилинах) потягів, що вирушають з Лугано. Вони задані в порядку зростання, тобто d_k < d_{k+1} для всіх допустимих .
Виведіть «YES» (без лапок), якщо відбудеться принаймні одне зіткнення, або «NO» інакше.
Приклад 1
Приклад 2
Приклад 3
Приклад 4
У першому прикладі є два тунелі на колії довжиною 100 кілометри: один від 20 до 30 кілометрів від Цюриха, інший від 50 до 60 кілометрів від Цюриха. Єдиному потягу, що відправляється з Цюриха, вдається уникнути всіх потягів у Лугано наступним чином:
перший зустрічається за 5 кілометрів від Цюриха,
другий зустрічається на півдорозі між тунелями,
третій зустрічається за 10 кілометрів від Лугано,
четвертий розпочинає задовго після того, як потяг з Цюриха прибув у пункт призначення.
У другому прикладі два потяги стикаються точно посередині єдиного тунелю, в результаті чого відбувається аварія.
У третьому прикладі два потяги стикаються точно в кінці тунелю, який знаходиться ближче до Цюриха. У четвертому прикладі вони зустрічаються точно на іншому кінці тунелю. Обидва випадки безпечні, оскільки потяги проїжджають один одного і безпечно добираються до місця призначення.
В усіх блоках, крім останнього, , всі c_j та всі d_k є парними.
Блок 1 (14 балів): t, m, n \leq 100 та s \leq 5\,000.
Блок 2 (16 балів): t \leq 5\,000 та s \leq 1\,000\,000.
Блок 3 (41 бал): без додаткових обмежень.
Блок 4 (29 балів): без додаткових обмежень. А також, , c_j та d_k не обов'язково парні.