eolymp
Competitions

European Girls' Olympiad in Informatics 2021, II Day

Залізниця

Між Цюрихом та Лугано пролягає залізниця довжиною $s$ кілометрів. Залізниця перетинає мальовничі Альпи, що призводить до вражаючих пейзажів під час їзди. Оскільки деякі перевали занадто високі для залізниці, на колії є $t$ тунелів. $i$-й з них починається на відстані $a_i$ кілометрів від Цюриха і закінчується на відстані $b_i$ кілометрів від Цюриха. (Таким чином, довжина $i$-го тунелю становить $b_i - a_i$.) У вас є розклад залізничного сполучення між двома містами. Існує $m$ потягів з Цюриха в Лугано, $j$-ий потяг відходить в $c_j$ хвилин. А також $n$ потягів з Лугано в Цюрих, $k$-ий потяг відправляється в $d_k$ хвилин. Усі потяги, що курсують на колії, мають постійну швидкість 1 кілометр на хвилину, незалежно від їхнього напрямку та від того, перебувають вони в тунелі чи ні. На маршруті немає станцій, і потяги ніколи не зупиняються у семафорах. Отже, кожен потяг прибуває до місця призначення рівно за $s$ хвилин. Довжина потяга незначна порівняно з довжиною залізниці, тому в цій задачі, \textbf{будь ласка, припустіть, що кожен потяг --- це точка}, яка рухається вздовж залізниці. Зазвичай залізниця має дві колії: по одній у кожному напрямку. Єдиним винятком є тунелі. Кожен тунель має лише одну колію, яку можна використовувати в будь-якому напрямку. Кожного разу, коли два потяги, що їдуть у протилежних напрямках, стикаються за межами тунелю, вони можуть безпечно проїжджати один одного. Сюди входять потяги, які збираються точно в кожному кінці тунелю. З іншого боку, якщо пара потягів зустрічається строго всередині тунелю, відбувається зіткнення. Враховуючи опис тунелів та поїздів, визначте, чи не відбудеться зіткнення. \InputFile Перший рядок містить чотири цілі числа $s$, $t$, $m$, $n$ ($1 \leq s \leq 1\,000\,000\,000$, $0 \leq t \leq 100\,000$, $0 \leq m, n \leq 2\,000$) --- довжина залізниці, кількість тунелів, кількість потягів з Цюриха та кількість потягів з Лугано відповідно. Другий рядок містить $t$ цілих чисел $a_i$ ($0 \leq a_i < s$) --- початкові позиції тунелів. Третій рядок містить $t$ цілих чисел $b_i$ ($0 < b_i \leq s$) --- кінцеві позиції тунелів. Для кожного $i$ від $1$ до $t$, виконується умова $a_i < b_i$. А також для кожного $i$ від $1$ до $t-1$, виконується умова $b_i < a_{i+1}$. (Іншими словами, кожен тунель має додатню довжину, тунелі не перетинаються, тунелі дані у порядку зростання відстані від Цюриха.) Четвертий рядок містить $m$ цілих чисел $c_j$ ($0 \leq c_j \leq 1\,000\,000\,000$) --- час початку (у хвилинах) потягів, що вирушають з Цюриха. Вони задані в порядку зростання, тобто $c_j < c_{j+1}$ для всіх валідних $j$. П'ятий рядок містить $n$ цілих чисел $d_k$ ($0 \leq d_k \leq 1\,000\,000\,000$) --- час початку (у хвилинах) потягів, що вирушають з Лугано. Вони задані в порядку зростання, тобто $d_k < d_{k+1}$ для всіх валідних $k$. \OutputFile Виведіть <<YES>> (без дужок), якщо відбудеться принаймні одне зіткнення, або <<NO>> інакше. \Note У першому прикладі є два тунелі на колії довжиною 100 кілометри: один від 20 до 30 кілометрів від Цюриха, інший від 50 до 60 кілометрів від Цюриха. Єдиному поїзду, що прибуває з Цюриха, вдається уникнути всіх рейсів у Лугано наступним чином: \begin{itemize} \item перший зустрічається за 5 кілометрів від Цюриха, \item другий зустрічається на півдорозі між тунелями, \item третій зустрічається за 10 кілометрів від Лугано, \item четвертий розпочинає задовго після того, як поїзд з Цюриха прибув у пункт призначення. \end{itemize} У другому прикладі два поїзди стикаються точно посередині єдиного тунелю, в результаті чого відбувається аварія. У третьому прикладі два поїзди стикаються точно в кінці тунелю, який знаходиться ближче до Цюриха. У четвертому прикладі вони зустрічаються точно на іншому кінці тунелю. Обидва випадки безпечні, оскільки поїзди проїжджають один одного і безпечно добираються до місця призначення. \Scoring В усіх блоках, крім останнього, $s$, всі $c_j$ та всі $d_k$ є \textbf{парними}. Блок 1 (14 балів): $t, m, n \leq 100$ and $s \leq 5\,000$. Блок 2 (16 балів): $t \leq 5\,000$ and $s \leq 1\,000\,000$. Блок 3 (41 бал): без додаткових обмежень. Блок 4 (29 балів): без додаткових обмежень. А також, $s$, $c_j$ та $d_k$ не обов'язково парні.
Time limit 2 seconds
Memory limit 256 MiB
Input example #1
100 2 1 4
20 50
30 60
120
30 100 200 250
Output example #1
NO
Input example #2
1000 1 1 1
600
700
100
400
Output example #2
YES
Input example #3
1000 1 1 1
600
700
100
300
Output example #3
NO
Input example #4
1000 1 1 1
600
700
100
500
Output example #4
NO
Author Anton Tsypko