Землетрясения в диапазоне
Сейсмологу нужен быстрый ответ на вопросы вида «сколько было землетрясений с магнитудой от a до b включительно». Каталог большой, а вопросов много — пересчитывать каталог для каждого вопроса не выйдет. Два теста — настоящий каталог USGS: все 19 073 землетрясения силой от 5 баллов за 2015–2025 годы.
Вход
В первой строке n (1 ≤ n ≤ 200 000), во второй — n магнитуд через пробел. В третьей — число вопросов q (1 ≤ q ≤ 200 000), дальше q строк по два числа a ≤ b. Все числа от 0 до 10 и записаны ровно с двумя знаками после точки.
Выход
Для каждого вопроса — число землетрясений с магнитудой m, для которой a ≤ m ≤ b, по одному в строке.
Примеры
Пример 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
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 6 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Если отсортировать магнитуды, все подходящие землетрясения окажутся подряд. Где начинается и где кончается этот кусок?
2Идея
Ответ на вопрос — длина куска отсортированного массива между нижней границей a (первый элемент ≥ a) и верхней границей b (первый элемент > b). Сортируем один раз, на каждый вопрос — два двоичных поиска.
3Разбор
Магнитуды записаны с двумя знаками, поэтому удобно сразу перевести их в целые сотые: 5,36 → 536. Тогда сравнения точные и не зависят от того, как процессор хранит 5,36 в двоичной дроби. В Python round(float(s) * 100) справляется, в Go надёжнее разобрать строку по точке.
Ответ на вопрос — bisect_right(mags, b) − bisect_left(mags, a). В Go то же самое — sort.SearchInts для нижней границы и sort.Search с условием «больше b» для верхней.
3+Решение
4Сложность
Сортировка O(n log n), вопрос — O(log n). Всего O((n + q) log n) — около семи миллионов сравнений при предельных размерах. Перебор каталога на каждый вопрос стоил бы 200 000 × 200 000 = 4·10¹⁰.
5Типичные ошибки
- Обе границы нижние.
bisect_left(b) − bisect_left(a)теряет землетрясения ровно с магнитудой b. В шестом тесте сто тысяч землетрясений силой ровно 6,00. - Сравнение дробей. Если хранить магнитуды как float и сравнивать с float из вопроса, всё обычно работает — но «обычно» в тестах на границах превращается в «почти». Целые сотые снимают вопрос.
- Медленный ввод. Четыреста тысяч чисел читать по одному через
input()— лишние секунды.