Earthquakes in a range
A seismologist needs quick answers to questions like “how many earthquakes had a magnitude from a to b inclusive”. The catalogue is big and the questions are many—recounting the catalogue for every question will not do. Two tests are the real USGS catalogue: all 19,073 earthquakes of magnitude 5 and above in 2015–2025.
Input
The first line holds n (1 ≤ n ≤ 200,000), the second n magnitudes separated by spaces. The third holds the number of questions q (1 ≤ q ≤ 200,000), followed by q lines of two numbers a ≤ b. All numbers are between 0 and 10 and written with exactly two digits after the point.
Output
For each question, the number of earthquakes with a magnitude m such that a ≤ m ≤ b, one per line.
Examples
Example 1
7 5.10 6.00 7.30 5.40 6.00 8.80 5.00 5 6.00 6.00 5.00 7.00 7.00 9.00 9.00 9.50 4.00 5.00
2 5 2 0 1
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 6 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
If you sort the magnitudes, all the matching earthquakes end up next to each other. Where does that run begin and where does it end?
2The idea
The answer to a question is the length of the run of the sorted array between the lower bound of a (the first element ≥ a) and the upper bound of b (the first element > b). Sort once; two binary searches per question.
3Walkthrough
Magnitudes are written with two digits, so it is convenient to turn them into whole hundredths at once: 5.36 → 536. Then comparisons are exact and do not depend on how the processor stores 5.36 as a binary fraction. In Python round(float(s) * 100) copes; in Go it is safer to split the string at the point.
The answer to a question is bisect_right(mags, b) − bisect_left(mags, a). In Go the same is sort.SearchInts for the lower bound and sort.Search with the condition “greater than b” for the upper one.
3+Solution
4Complexity
Sorting is O(n log n), a question O(log n). In all O((n + q) log n)—about seven million comparisons at the largest sizes. Scanning the catalogue for every question would cost 200,000 × 200,000 = 4·10¹⁰.
5Common mistakes
- Both bounds lower.
bisect_left(b) − bisect_left(a)loses the earthquakes of magnitude exactly b. The sixth test has a hundred thousand earthquakes of exactly 6.00. - Comparing fractions. Keeping magnitudes as floats and comparing them with floats from the question usually works—but on boundary tests “usually” turns into “almost”. Whole hundredths settle it.
- Slow input. Reading four hundred thousand numbers one by one with
input()costs extra seconds.