История изменений

о, не сразу заметил что там еще и ограничение на n*q. Ну тогда все совсем просто. Сортируем оба массива и для каждого запроса делаем бинпоиск «количество дробей меньше заданной» по вещественному значению дроби (меньше 10**6). На каждой итерации бинпоиска проходим по всем знаменателям и находим, на какой позиции находится первый (или последний) подходящий числитель. Это можно сделать двумя указателями.

Итоговая сложность n*q*log(10**6) без выделения дополнительной памяти - должно пройти. Если не пройдет из-за точности, то авторов задачи следует скормить мелкозявру айронбага.

о, не сразу заметил что там еще и ограничение на n*q. Ну тогда все совсем просто. Сортируем оба массива и для каждого запроса делаем бинпоиск «количество дробей меньше заданной» по вещественному значению дроби (меньше 10**6). На каждой итерации бинпоиска проходим по всем знаменателям и находим, на какой позиции находится первый (или последний) подходящий числитель. Это можно сделать двумя указателями.

Итоговая сложность nqlog(10**6) без выделения дополнительной памяти - должно пройти. Если не пройдет из-за точности, то авторов задачи следует скормить мелкозявру айронбага.