Número más pequeño

Points: 100 (partial)

Time limit: 2.0s

Memory limit: 128M

Authors:

FrankHG, rafael

Problem type

Allowed languages

Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

A Bitman le gusta jugar con listas de números distintos de cero. El tiene muchas de tales listas. Para matar el aburrimiento, el toma alguna lista y busca el $k^{th}$ ~k^{th}~ número más pequeño en esta. Sin embargo, pronto perdió el interés en hacerlo porque era demasiado fácil, por lo que decidió crear una nueva lista $L$ ~L~ utilizando este procedimiento:

- las listas son 1-indexadas -
procedimiento GenerarLista (A, B, x):
   sea n = longitud de A
   sea m = longitud de B
   sea L = una lista vacía
   para i de 1 a min (n, m - x), inclusive:
       para j desde (i + x) hasta m, inclusive:
          Agregue (A[i] * B[j]) al final de L
   devolver L

Para crear L, el toma dos listas A y B y un entero x y llama al subprograma $GenerarLista (A, B, x)$ ~GenerarLista (A, B, x)~. El estaba sorprendido al ver una lista tan grande y decidió encontrar el $k^{th}$ ~k^{th}~ número más pequeño en esta. Puede usted ayudarlo ?

Observe que $k^{th}$ ~k^{th}~ número más pequeño en una lista L es el $k^{th}$ ~k^{th}~ elemento de L cuando esta es ordenada. Por ejemplo, el $4^{th}$ ~4^{th}~ número más pequeño en $[7,2,7,2,11]$ ~[7,2,7,2,11]~ es 7.

Entrada

La primera línea contiene cuatro enteros n, m, x y k separados entre si por espacios. Los tamaños respectivos de $A$ ~A~ y $B$ ~B~ son n y m. La segunda línea contiene n enteros $A_1, A_2, ..., A_n$ ~A_1, A_2, ..., A_n~ separados entre si por espacio en blanco. La tercera línea contiene m enteros $B_1, B_2, ..., B_m$ ~B_1, B_2, ..., B_m~ separados entre si por espacio en blanco.

Restricciones

$2 \leq n,m \leq 2.10^5$ ~2 \leq n,m \leq 2.10^5~
$1 \leq x < m$ ~1 \leq x < m~
$1 \leq |A_i| \leq 2.10^5$ ~1 \leq |A_i| \leq 2.10^5~
$1 \leq |B_i| \leq 2.10^5$ ~1 \leq |B_i| \leq 2.10^5~
$1 \leq k \leq longitud(L)$ ~1 \leq k \leq longitud(L)~

Salida

Imprimir una sola línea que contenga un entero denotando la respuesta: el $k^{th}$ ~k^{th}~ número más pequeño en la lista L.

Ejemplo de Entrada

3 4 1 5
2 -3 1
3 1 -2 -1

Ejemplo de Salida

Explicación

La lista L se obtiene después de llamar a $GenerarLista([2,-3,1],[3,1,-2,-1],1)$ ~GenerarLista([2,-3,1],[3,1,-2,-1],1)~. Encontramos que $L=[2,-4-2,6,3,-1]$ ~L=[2,-4-2,6,3,-1]~. Por lo tanto, el $5^{th}$ ~5^{th}~ número más pequeño en L es 3.

Comments

5

aniervs commented on April 2, 2020, 1:31 a.m.

Búsqueda binaria: digamos que $f(r)$ ~f(r)~ es la cantidad de números en la lista menores o iguales a $r$ ~r~; es obvio que $f(r)$ ~f(r)~ es no decreciente, así que puedes aplicar búsqueda binaria para encontrar el menor $r$ ~r~ tal que $f(r)\ge k$ ~f(r)\ge k~. Ahora solo necesitas computar $f(r)$ ~f(r)~, iteramos por las $i \in [1,\min(m-x,n)]$ ~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$ ~j\ge i+x: a[i]\cdot b[j] \le r~.

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

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

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

Entonces podemos mantener un ABI, y si iteramos por $i$ ~i~ decrecientemente para un $i$ ~i~ tenemos en el ABI a $b[i+x], b[i+x+1], \dots, b[m]$ ~b[i+x], b[i+x+1], \dots, b[m]~, entonces para $i-1$ ~i-1~ solo tenemos que agregar $b[i+x-1]$ ~b[i+x-1]~. Hacemos $O(n\cdot \log n)$ ~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)$ ~O(n\cdot \log^2 n)~.

0

dmesadiaz commented on April 9, 2020, 7:50 a.m.

Man disculpa la molestia pero como tu haces para crear ese ABI con los valores negativos yo la función del ABI la quise hacer con un persistent pero se me marea con los valores negativos.

1

aniervs commented on April 10, 2020, 4:07 a.m.

Yo lo programé usando dos ABI, uno para los negativos y uno para los positivos, pero puedes tener un solo sumándole $2\cdot 10^5 +1$ ~2\cdot 10^5 +1~ a cada valor, así cuando vayas a sumarle 1 a la posición $a$ ~a~ lo que haces sumar 1 en la posición $a+2\cdot 10^5+1$ ~a+2\cdot 10^5+1~.

0

Primervirgen commented on April 4, 2020, 7:20 p.m.

Gracias men

1

aniervs commented on April 5, 2020, 12:29 a.m.

Si necesitas más detalles solo dilo.

0

Primervirgen commented on March 30, 2020, 6:30 a.m.

Alguna idea d como hacer este problema?

1

aniervs commented on April 2, 2020, 1:31 a.m.

te lo puse arriba