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 and . In classroom , the teacher will show different slides during the class, with the slide shown throughout the exclusive time interval where and 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 and , or the pair and , but not the pair and .
You begin the day in classroom with both classes starting at time . 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 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 seconds and are thus unable to see any slides.
For example, if classroom has a slide being shown for the time interval , classroom has a slide being shown for the time interval , and , then you'll get to see both slides if you move from classroom to classroom at time seconds (arriving at time seconds). On the other hand, if you leave classroom at time seconds (arriving at time seconds), then you'll enter classroom 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 , , and .
The next lines each contain two space-separated integers and .
The next lines each contain two space-separated integers, and .
|Marks Awarded||Bounds on||Bounds on and||Bounds on|
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
Explanation of Output for Sample Input 1
One possible optimal strategy is to remain in classroom until time , then move to classroom (arriving at time ), remain there until time , and finally return to classroom (arriving at time ). In the process, you'll see all but the 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
Explanation of Output for Sample Input 2
Even if you begin moving to classroom immediately at the start of the classes (e.g., at time ), you'll miss the first slides shown there. As such, it is possible to see a total of at most four slides.