Número más pequeño


Submit solution


Points: 100 (partial)
Time limit: 2.0s
Memory limit: 128M

Authors:
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} 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 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). El estaba sorprendido al ver una lista tan grande y decidió encontrar el k^{th} número más pequeño en esta. Puede usted ayudarlo ?

Observe que k^{th} número más pequeño en una lista L es el k^{th} elemento de L cuando esta es ordenada. Por ejemplo, el 4^{th} número más pequeño en [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 y B son n y m. La segunda línea contiene n enteros 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 separados entre si por espacio en blanco.

Restricciones

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

Salida

Imprimir una sola línea que contenga un entero denotando la respuesta: el 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

3

Explicación

La lista L se obtiene después de llamar a GenerarLista([2,-3,1],[3,1,-2,-1],1). Encontramos que L=[2,-4-2,6,3,-1]. Por lo tanto, el 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) 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).


    • 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 a cada valor, así cuando vayas a sumarle 1 a la posición a lo que haces sumar 1 en la posición 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