Railway#10663
The railway line between Zurich and Lugano spans a distance of kilometers. The railway crosses the picturesque Alps, which leads to stunning views during the journey. Since some passes are too high for the railway, there are tunnels on the track. The -th tunnel starts at a distance of a_i kilometers from Zurich and ends at a distance of b_i kilometers from Zurich. (Thus, the length of the -th tunnel is b_i - a_i.)
You have a railway timetable between the two cities. There are trains from Zurich to Lugano, the -th train departs at c_j minutes. There are also trains from Lugano to Zurich, the -th train departs at d_k minutes. All trains traveling on the track have a constant speed of 1 kilometer per minute, regardless of their direction and whether they are in a tunnel or not. There are no stations on the route, and trains never stop at signals. Therefore, each train arrives at its destination in exactly minutes.
The length of a train is negligible compared to the length of the railway, so in this problem, please assume that each train is a point moving along the railway.
Usually, a railway has two tracks: one in each direction. The only exception is the tunnels. Each tunnel has only one track, which can be used in either direction.
Whenever two trains traveling in opposite directions meet outside a tunnel, they can safely pass each other. This includes trains that meet exactly at either end of a tunnel. On the other hand, if a pair of trains meets strictly inside a tunnel, a collision occurs.
Given the description of the tunnels and trains, determine whether a collision will occur.
The first line contains four integers , , , (1 \leq s \leq 1\,000\,000\,000, 0 \leq t \leq 100\,000, 0 \leq m, n \leq 2\,000) — the length of the railway, the number of tunnels, the number of trains from Zurich and the number of trains from Lugano respectively.
The second line contains integers a_i (0 \leq a_i < s) — the starting positions of the tunnels.
The third line contains integers b_i (0 < b_i \leq s) — the ending positions of the tunnels.
For each from to , the condition a_i < b_i holds. Also, for each from to t-1, the condition b_i < a_{i+1} holds. (In other words, each tunnel has a positive length, tunnels do not overlap, and tunnels are given in increasing order of distance from Zurich.)
The fourth line contains integers c_j (0 \leq c_j \leq 1\,000\,000\,000) — the departure times (in minutes) of the trains leaving Zurich. They are given in increasing order, i.e., c_j < c_{j+1} for all valid .
The fifth line contains integers d_k (0 \leq d_k \leq 1\,000\,000\,000) — the departure times (in minutes) of the trains leaving Lugano. They are given in increasing order, i.e., d_k < d_{k+1} for all valid .
Print "YES" (without quotes) if at least one collision will occur, or "NO" otherwise.
Example 1
Example 2
Example 3
Example 4
In the first example, there are two tunnels on a 100-kilometer track: one from 20 to 30 kilometers from Zurich, another from 50 to 60 kilometers from Zurich. The only train departing from Zurich manages to avoid all trains to Lugano as follows:
the first is met 5 kilometers from Zurich,
the second is met halfway between the tunnels,
the third is met 10 kilometers from Lugano,
the fourth departs long after the train from Zurich has arrived at its destination.
In the second example, two trains collide exactly in the middle of the only tunnel, resulting in a crash.
In the third example, two trains meet exactly at the end of the tunnel that is closer to Zurich. In the fourth example, they meet exactly at the other end of the tunnel. Both cases are safe, since the trains pass each other and safely reach their destinations.
In all blocks except the last one, , all c_j and all d_k are even.
Block 1 (14 points): t, m, n \leq 100 and s \leq 5\,000.
Block 2 (16 points): t \leq 5\,000 and s \leq 1\,000\,000.
Block 3 (41 points): no additional constraints.
Block 4 (29 points): no additional constraints. Also, , c_j and d_k are not necessarily even.