Want to try solving this problem? You can submit your code online if you log in or register.

**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 *k*th of
these lines will be of the form *a _{k} b_{k}*,
where Jean-David enters Hyde
Park at time

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 *k*th of
these lines will be of the form *c _{k} d_{k}*,
where Sir Geoffrey enters Hyde
Park at time

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
*a*_{1} < *b*_{1} < *a*_{2} < *b*_{2} < ... < *a _{j}* <

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

15

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.

Privacy
statement

© Australian Mathematics Trust 2001-2024

Page generated: 13 April 2024, 7:00am AEST