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

Такое в мыслях витало, но вы хорошо выразили. Правда почему именно 5000 я не понял. Я это сейчас вижу так:

0. Соритируем a,b.
1. Берем любую дробь m, допустим по середине a[n/2] / b[n/2].
2. Введем число d, которое будет означать сколько дробей менее m.
3. Проходимся бинарным поиском внутри каждой группы с одинаковым знаменателем. И для каждой группы находим сколько значений менее m. Назовем это число для каждой группы n_i.
4. Очевидно, что если d > c(запрос), то нужно число большее m, в противном случае, нужно число большее m.
5. Для каждой группы имеем по одному кандидату. По сути это либо n_i либо n_i-1. В зависимости от условия 4.
6. Имея n кандидатов, выбираем тот который ближе всего находится к m. m = new_candidate.
7. Повторяем шаги 2-6 пока d != c.

Я отпишу реализацию чуть позже. В реализации нужно ещё аккуратно с индексами кандидатов, чтобы за границы не уйти.

n_i - 1

Такое в мыслях витало, но вы хорошо выразили. Правда почему именно 5000 я не понял. Я это сейчас вижу так:

0. Соритируем a,b.
1. Берем любую дробь m, допустим по середине a[n/2] / b[n/2].
2. Введем число d, которое будет означать сколько дробей менее m.
3. Проходимся бинарным поиском внутри каждой группы с одинаковым знаменателем. И для каждой группы находим сколько значений менее m. Назовем это число для каждой группы n_i.
4. Очевидно, что если d > c(запрос), то нужно число большее m, в противном случае, нужно число большее m.
5. Для каждой группы имеем по одному кандидату. По сути это либо n_i либо n_i-1. В зависимости от условия 4.
6. Имея n кандидатов, выбираем тот который ближе всего находится к m. m = new_candidate.
7. Повторяем шаги 2-6 пока d != c.

Я отпишу реализацию чуть позже.