CCO '22 P3 - Double Attendance

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 3.0s
Memory limit: 1G

Author:
Problem types
Canadian Computing Olympiad: 2022 Day 1, Problem 3

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?

Input Specification

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).

Marks AwardedBounds on N_iBounds on A_{i,j} and B_{i,j}Bounds on K
5 marks1 \le N_i \le 100 \le A_{i,j} < B_{i,j} \le 2\,0001 \le K \le 10^9
10 marks1 \le N_i \le 2\,0000 \le A_{i,j} < B_{i,j} \le 2\,0001 \le K \le 10^9
6 marks1 \le N_i \le 2\,0000 \le A_{i,j} < B_{i,j} \le 10^9, B_{i,j}-A_{i,j} \le 2K1 \le K \le 10^9
4 marks1 \le N_i \le 300\,0000 \le A_{i,j} < B_{i,j} \le 10^91 \le K \le 10^9

Output Specification

Output one integer which is the maximum number of distinct slides which you can see.

Sample Input 1

3 1 8
10 20
100 101
20 21
15 25

Output for Sample Input 1

3

Explanation of Output for Sample Input 1

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.

Sample Input 2

1 5 3
1 100
1 2
2 3
3 4
4 5
5 6

Output for Sample Input 2

4

Explanation of Output for Sample Input 2

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.


Comments

There are no comments at the moment.