| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 54 | 10 | 9 | 17.308% |
Due to a rather ambitious school schedule, two of your classes are about to be held starting at exactly the same time, in two different classrooms! You can only be in one place at a time, so the best you can hope for is catching the important bits of both, even if that means sneaking back and forth between the two.
The two classrooms are numbered 1ドル$ and 2ドル$. In classroom $i,ドル the teacher will show $N_i$ different slides during the class, with the $j^\text{th}$ slide shown throughout the exclusive time interval $( A_{i,j}, B_{i,j})$ $(0 \le A_{i,j} < B_{i,j})$ where $A_{i,j}$ and $B_{i,j}$ are times elapsed since the start of class measured in seconds. In both classes, there does not exist a point in time at which multiple slides are simultaneously being shown. For example, a class may have slides spanning the pair of intervals $(1, 2)$ and $(5, 6),ドル or the pair $(10, 20)$ and $(20, 30),ドル but not the pair $(10, 20)$ and $(19, 30)$.
You begin the day in classroom 1ドル$ with both classes starting at time 0ドル$. Following that, at any point in time (not necessarily after an integral number of seconds), you may move from your current classroom to the other one in $K$ seconds. You consider yourself to have seen a slide if you spend a positive amount of time in its classroom strictly within the time interval during which it's being shown. When moving between the two classrooms, you're not considered to be inside either of them for $K$ seconds and are thus unable to see any slides.
For example, if classroom 1ドル$ has a slide being shown for the time interval $(10, 20),ドル classroom 2ドル$ has a slide being shown for the time interval $(15, 25),ドル and $K = 8,ドル then you'll get to see both slides if you move from classroom 1ドル$ to classroom 2ドル$ at time 11ドル.5$ seconds (arriving at time 19ドル.5$ seconds). On the other hand, if you leave classroom 1ドル$ at time 17ドル$ seconds (arriving at time 25ドル$ seconds), then you'll enter classroom 2ドル$ just after its slide stops being shown and will therefore miss it.
What's the maximum number of distinct slides which you can see at least once?
The first line contains three space-separated integers $N_1,ドル $N_2,ドル and $K$.
The next $N_1$ lines each contain two space-separated integers $A_{1,i}$ and $B_{1,i}$ $(1 \le i \le N_1)$.
The next $N_2$ lines each contain two space-separated integers, $A_{2, i}$ and $B_{2,i}$ $(1 \le i \le N_2)$.
Output one integer which is the maximum number of distinct slides which you can see.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | 1ドル \le N_i \le 10,ドル 0ドル \le A_{i,j} < B_{i, j} \le 2,000円,ドル 1ドル \le K \le 10^9$ |
| 2 | 10 | 1ドル \le N_i \le 2,000円,ドル 0ドル \le A_{i,j} < B_{i, j} \le 2,000円,ドル 1ドル \le K \le 10^9$ |
| 3 | 6 | 1ドル \le N_i \le 2,000円,ドル 0ドル \le A_{i,j} < B_{i, j} \le 10^9,ドル $B_{i, j} - A_{i, j} \le 2K,ドル 1ドル \le K \le 10^9$ |
| 4 | 4 | 1ドル \le N_i \le 300,000円,ドル 0ドル \le A_{i,j} < B_{i, j} \le 10^9,ドル 1ドル \le K \le 10^9$ |
3 1 8 10 20 100 101 20 21 15 25
3
One possible optimal strategy is to remain in classroom 1ドル$ until time 11ドル.5,ドル then move to classroom 2ドル$ (arriving at time 19ドル.5$), remain there until time 19ドル.6,ドル and finally return to classroom 1ドル$ (arriving at time 27ドル.6$). In the process, you'll see all but the 3ドル^\text{rd}$ slide. It's impossible for you to see all 4 slides.
1 5 3 1 100 1 2 2 3 3 4 4 5 5 6
4
Even if you begin moving to classroom 2ドル$ immediately at the start of the classes (e.g., at time 0ドル.0001$), you'll miss the first 2ドル$ slides shown there. As such, it is possible to see a total of at most four slides.