Búsqueda binaria: digamos que ~f(r)~ es la cantidad de números en la lista menores o iguales a ~r~; es obvio que ~f(r)~ es no decreciente, así que puedes aplicar búsqueda binaria para encontrar el menor ~r~ tal que ~f(r)\ge k~. Ahora solo necesitas computar ~f(r)~, iteramos por las ~i \in [1,\min(m-x,n)]~ y para cada una tenemos que contar cuántas ~j\ge i+x: a[i]\cdot b[j] \le r~.

Si ~a[i] = 0~: contamos todos los ~j \ge i + x~ si ~r \ge 0~, ya que ~b[j]\cdot a[i] = 0~; si ~r < 0~ no contamos niguno.

Si ~a[i] > 0~: tenemos que contar cuántas ~j\ge i+x:b[j] \le \frac{r}{a[i]}~.

Si ~a[i] < 0~: tenemos que contar cuántas ~j\ge i+x:b[j] \ge \frac{r}{a[i]}~.

Entonces podemos mantener un ABI, y si iteramos por ~i~ decrecientemente para un ~i~ tenemos en el ABI a ~b[i+x], b[i+x+1], \dots, b[m]~, entonces para ~i-1~ solo tenemos que agregar ~b[i+x-1]~. Hacemos ~O(n\cdot \log n)~ operaciones en cada momento de la búsqueda binaria, por lo que corre en tiempo ~O(n\cdot \log^2 n)~.