Dəmir yolu#10663
Цюrix ilə Luqano arasında uzunluğu kilometr olan dəmir yolu uzanır. Bu dəmir yolu mənzərəli Alp dağlarından keçir, səyahət zamanı təsirli mənzərələr təqdim edir. Bəzi keçidlər dəmir yolu üçün çox yüksək olduğundan, yolda tunel var. -ci tunel Цюrixdən a_i kilometr məsafədə başlayır və Цюrixdən b_i kilometr məsafədə bitir. (Beləliklə, -ci tunelin uzunluğu b_i - a_i-dir.)
Sizin Цюrix ilə Luqano arasında dəmir yolu cədvəliniz var. Цюrixdən Luqanoya qatar var, -ci qatar c_j dəqiqədə yola düşür. Həmçinin, Luqanodan Цюrixə qatar var, -ci qatar d_k dəqiqədə yola düşür. Yolda hərəkət edən bütün qatarlar istiqamətindən və tuneldə olub-olmamasından asılı olmayaraq, sabit sürətlə, dəqiqədə 1 kilometr sürətlə hərəkət edir. Marşrutda stansiyalar yoxdur və qatarlar heç vaxt semaforlarda dayanmır. Beləliklə, hər bir qatar təyinat yerinə dəqiq dəqiqə ərzində çatır.
Qatarın uzunluğu dəmir yolunun uzunluğu ilə müqayisədə əhəmiyyətsizdir, buna görə də bu məsələdə, zəhmət olmasa, hər bir qatarın dəmir yolu boyunca hərəkət edən bir nöqtə olduğunu fərz edin.
Adətən dəmir yolu iki xəttə malikdir: hər istiqamətdə bir xətt. Yeganə istisna tunellərdir. Hər bir tunel yalnız bir xəttə malikdir və bu xətt hər iki istiqamətdə istifadə edilə bilər.
Hər dəfə əks istiqamətlərdə hərəkət edən iki qatar tuneldən kənarda qarşılaşdıqda, onlar təhlükəsiz şəkildə bir-birini keçə bilərlər. Bu, tunelin hər iki ucunda dəqiq qarşılaşan qatarları da əhatə edir. Digər tərəfdən, əgər bir qatar cütü tunelin içərisində dəqiq qarşılaşırsa, toqquşma baş verir.
Tunellərin və qatarların təsvirini nəzərə alaraq, toqquşmanın olub-olmadığını müəyyən edin.
Birinci sətir dörd tam ədəd , , , (1 \leq s \leq 1\,000\,000\,000, 0 \leq t \leq 100\,000, 0 \leq m, n \leq 2\,000) — dəmir yolunun uzunluğu, tunellərin sayı, Цюrixdən qatarların sayı və Luqanodan qatarların sayı.
İkinci sətir tam ədəd a_i (0 \leq a_i < s) — tunellərin başlanğıc mövqelərini ehtiva edir.
Üçüncü sətir tam ədəd b_i (0 < b_i \leq s) — tunellərin son mövqelərini ehtiva edir.
Hər bir üçün -dən -ə qədər, a_i < b_i şərti yerinə yetirilir. Həmçinin hər bir üçün -dən t-1-ə qədər, b_i < a_{i+1} şərti yerinə yetirilir. (Başqa sözlə, hər bir tunelin müsbət uzunluğu var, tunellər kəsişmir, tunellər Цюrixdən məsafənin artma sırasına görə verilmişdir.)
Dördüncü sətir tam ədəd c_j (0 \leq c_j \leq 1\,000\,000\,000) — Цюrixdən yola düşən qatarların başlanğıc vaxtını (dəqiqə ilə) ehtiva edir. Onlar artma sırasına görə verilir, yəni c_j < c_{j+1} bütün uyğun üçün.
Beşinci sətir tam ədəd d_k (0 \leq d_k \leq 1\,000\,000\,000) — Luqanodan yola düşən qatarların başlanğıc vaxtını (dəqiqə ilə) ehtiva edir. Onlar artma sırasına görə verilir, yəni d_k < d_{k+1} bütün uyğun üçün.
Ən azı bir toqquşma baş verərsə, "YES" (dırnaqsız) çıxarın, əks halda "NO" çıxarın.
Nümunə 1
Nümunə 2
Nümunə 3
Nümunə 4
Birinci nümunədə Цюrixdən 100 kilometr uzunluğunda yolda iki tunel var: biri Цюrixdən 20-dən 30 kilometrə qədər, digəri Цюrixdən 50-dən 60 kilometrə qədər. Цюrixdən gələn yeganə qatar Luqanoya gedən bütün qatarları aşağıdakı kimi qarşısını alır:
birinci Цюrixdən 5 kilometr məsafədə qarşılaşır,
ikinci tunellər arasında yarı yolda qarşılaşır,
üçüncü Luqanodan 10 kilometr məsafədə qarşılaşır,
dördüncü Цюrixdən gələn qatar təyinat yerinə çatdıqdan çox sonra başlayır.
İkinci nümunədə iki qatar yeganə tunelin ortasında dəqiq qarşılaşır və nəticədə qəza baş verir.
Üçüncü nümunədə iki qatar Цюrixə daha yaxın olan tunelin sonunda dəqiq qarşılaşır. Dördüncü nümunədə onlar tunelin digər ucunda dəqiq qarşılaşır. Hər iki hal təhlükəsizdir, çünki qatarlar bir-birini keçərək təhlükəsiz şəkildə təyinat yerinə çatır.
Son blokdan başqa bütün bloklarda , bütün c_j və bütün d_k cütdür.
Blok 1 (14 bal): t, m, n \leq 100 və s \leq 5\,000.
Blok 2 (16 bal): t \leq 5\,000 və s \leq 1\,000\,000.
Blok 3 (41 bal): əlavə məhdudiyyətlər yoxdur.
Blok 4 (29 bal): əlavə məhdudiyyətlər yoxdur. Həmçinin, , c_j və d_k mütləq cüt deyil.