Viewership Popularity Survey
Time limit1sMemory limit128 MB
Given N viewing intervals (possibly wrapping past midnight) over a day, use a difference array over seconds to answer Q sum-of-popularity queries divided by interval length.
- Level
Medium5 of 10
- Topics
- Prefix sum, Array, Simulation
- Solved
- No attempts yet
Problem
A population survey was recently held in a country. Its real purpose was to measure television viewership popularity from the number of people watching at each second.
Each person's viewing interval is given in the following format.
HH:MM:SS - HH:MM:SS
The first time is when the person started watching, and the second time is when they stopped watching. The seconds at both the start time and the end time are included. If the ending time is earlier than the starting time, the person watched past midnight until that time on the next day.
The popularity of a second is the number of people watching television during that second. The popularity of an interval is the sum of the popularity values of all seconds in the interval divided by the interval length in seconds.
Given Q query intervals, compute the average popularity of each interval.
Input
The first line contains the number of people N. (N ≤ 100,000)
Each of the next N lines contains one person's television viewing interval in the form HH:MM:SS - HH:MM:SS. Each time satisfies 0 ≤ HH ≤ 23, 0 ≤ MM ≤ 59, and 0 ≤ SS ≤ 59.
The next line contains the number of query intervals Q. (Q ≤ 100,000)
Each of the next Q lines contains an interval in the same format for which the popularity must be computed.
Output
Print Q lines, one for each query interval, containing its popularity. Answers with an absolute or relative error of at most 10^-6 are accepted.