El Conejo Saltarín


Submit solution


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

Authors:
Problem type
Allowed languages
C++

El conejo saltarín se encuentra tranquilamente saltando en una hilera de n piedras, numeradas de 1 a n, donde a_i es la posición de la i-ésima piedra.

Se garantiza que a_i > a_{i-1} para todo 2 \leq i \leq n, es decir, la posición de una piedra es mayor que la de la piedra anterior.

El conejo tiene un límite de salto k, por lo que puede realizar un salto de la piedra x a la piedra y si y solo si | a_x - a_y | \leq k.

El conejo tiene q consultas de la forma x, y, quiere saber cuál es la mínima cantidad de saltos que debe realizar para ir de la piedra x a la piedra y, o si es imposible hacer esto, saltando solamente entre piedras.

Entrada:

La primera línea contendrá dos enteros n y k (2 \leq n \leq 200\,000), (1 \leq k \leq 200\,000), la cantidad de piedras y el límite de salto del conejo respectivamente.

La segunda línea contendrá n enteros a_1, a_2, \cdots, a_n (1 \leq a_i \leq 200\,000), donde a_i es la posición de la i-ésima piedra, se garantiza que a_i > a_{i-1} para todo 2 \leq i \leq n.

La tercera línea contendrá un entero q (1 \leq q \leq 200\,000), la cantidad de consultas a procesar.

Cada una de las siguientes q líneas contendrá dos enteros x y y (1 \leq x \leq y \leq n), las dos piedras de dicha consulta.

Salida

Imprima q líneas con un entero cada una, el resultado de cada consulta, la mínima cantidad de saltos que debe realizar el conejo para ir de la piedra x a la piedra y, o -1 si es imposible ir de x a y.

Subtareas:

  • Subtarea 1: a = 1, 2, \cdots, n, es decir, a es una permutación ascendente (10 puntos)
  • Subtarea 2: Se garantiza que existe un entero positivo const, tal que a_i - a_{i-1} = const para todo 2 \leq i \leq n (10 puntos)
  • Subtarea 3: Se garantiza que n \cdot q \leq 1\,000\,000 (28 puntos)
  • Subtarea 4: k \geq 10\,000, q \leq 10\,000 (27 puntos)
  • Subtarea 5: Sin restricciones adicionales (25 puntos)

Ejemplo de entrada:

7 4
1 5 8 9 10 12 17
5
1 6
2 6
3 5
4 6
1 7

Ejemplo de salida:

3
2
1
1
-1

Comments


  • -1
    legion06  commented on April 1, 2023, 8:56 p.m.

    alguien puede revisar mi programa para la segunda subatarea pq creo yo que si la const es mayor que k deberia imprimir -1