Input File: spiesin.txt
Output File: spiesout.txt
Time Limit: 4 seconds
It has taken half your life, but you are close to tracking down the ringleaders of Intricatus Mathematicae, a secret organisation sworn to protect the origins of the number pi. You have followed the leaders Jean-David and Sir Geoffrey, and you know that they plan to meet in Hyde Park to discuss their plots. It is vital that you know when they meet, how often they meet, and how long these meetings last.
You assign your best agents to track Jean-David and Sir Geoffrey's movements. Your agents note each time Jean-David enters or leaves the park, as well as each time Sir Geoffrey enters and leaves the park. It is your task to combine this information and determine the total amount of time for which both Jean-David and Sir Geoffrey were in the park together.
The input file will contain the information given to you by your agents. The first part of this file will describe the movements of Jean-David, and the second part will describe the movements of Sir Geoffrey.
The first line of input will contain the single integer j, representing the number of times that Jean-David enters and exits Hyde Park (0 <= j <= 1,000,000). Following this will be j lines, each describing a single entry and exit. Specifically, the kth of these lines will be of the form ak bk, where Jean-David enters Hyde Park at time ak and leaves at time bk.
After this will be a single line of input containing the single integer g, representing the number of times that Sir Geoffrey enters and exits Hyde Park (0 <= g <= 1,000,000). This will be followed by g additional lines of input, each describing a single entry and exit. The kth of these lines will be of the form ck dk, where Sir Geoffrey enters Hyde Park at time ck and leaves at time dk.
All times are measured in minutes since the beginning of the operation, and lie between 0 and 10,000,000 inclusive. The entry and exit times for Jean-David are given in chronological order (so that a1 < b1 < a2 < b2 < ... < aj < bj). Likewise, the entry and exit times for Sir Geoffrey are given in chronological order (so that c1 < d1 < c2 < d2 < ... < cg < dg).
Your output must consist of a single line containing a single integer, which is the total number of minutes that Jean-David and Sir Geoffrey spent in Hyde Park together.
3 10 20 40 60 85 100 2 15 50 110 120
In the example above, Jean-David makes three visits to Hyde Park (at times 10-20, 40-60 and 85-100) while Sir Geoffrey makes two visits (at times 15-50 and 110-120).
During Sir Geoffrey's first visit, he is present for the last five minutes of Jean-David's first visit (time 15-20) and the first ten minutes of Jean-David's second visit (time 40-50). During Sir Geoffrey's second visit he does not meet Jean-David at all. Thus Jean-David and Sir Geoffrey have spent a total of 15 minutes in the park together.
The score for each input file will be 100% if the correct answer is written to the output file and 0% otherwise.