Buscando compradores

Points: 100 (partial)

Time limit: 3.0s

Java 8 5.0s

Python 7.0s

Memory limit: 64M

Author:

ralcolea

Problem type

Allowed languages

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

Hay N compradores de pie en una línea, convenientemente numerados del 1 al N según su posición de izquierda a derecha. Cada comprador está dispuesto a comprar cualquier casa con un precio menor o igual a una cantidad positiva de dinero que posee.

La compañía C&N venderá H casas. Para cada casa, se elige un precio P y un rango (par de valores A y B) de posiciones, a fin de determinar quién podría ser el comprador potencial de esa casa. El comprador potencial de una casa será el comprador más a la izquierda con una posición entre A y B (ambos inclusive) que está dispuesto a pagar el precio de esa casa (es decir, tiene una cantidad de dinero mayor o igual a la cantidad necesaria para comprar la casa).

Dada la cantidad de dinero que tiene cada comprador, el precio y el rango seleccionado de posiciones para cada casa, usted tiene que encontrar quién será el comprador potencial de cada casa. Tenga en cuenta que la cantidad de dinero de cada comprador no disminuirá de ninguna manera. C&N está realizando únicamente un estudio para determinar los mejores precios de venta para sus casas.

Entrada

La primera línea contiene un entero $N (1 \le N \le 10^5)$ ~N (1 \le N \le 10^5)~, que representa el número de compradores. La segunda línea tiene N números enteros $Ci (1 \le Ci \le 10^6$ ~Ci (1 \le Ci \le 10^6~, para $i$ ~i~ entre $1$ ~1~ y $N$ ~N~) separados por un espacio que representan la cantidad de dinero de cada comprador, de izquierda a derecha. La siguiente línea contiene un número entero $H (1 \le H \le 10^5)$ ~H (1 \le H \le 10^5)~ que representa el número de casas. Las siguientes líneas H contienen tres números enteros separados por un espacio $P (1 \le P \le 10^6)$ ~P (1 \le P \le 10^6)~, $A$ ~A~ y $B (1 \le A \le B \le N)$ ~B (1 \le A \le B \le N)~, que representan el precio de una casa y el rango seleccionado de posiciones para compradores.

Salida

Usted debe imprimir la salida de las $H$ ~H~ líneas; en cada caso, con la posición de quien será el comprador potencial de cada casa. Imprima $-1$ ~-1~ si, por alguna razón, no hay compradores en el rango seleccionado con suficiente dinero para pagar la casa.

Ejemplo de entrada

10
213 32 52 4524 4 445 565 45 45 199
5
10 1 10
343 5 8
5235 1 10
40 8 9
100 9 10

Ejemplo de salida

Comments

0

Hd commented on Dec. 23, 2023, 4:17 a.m. ← edited →

Yo lo resolví con un Segment Tree con ciertas modificaciones

1

elio commented on Feb. 8, 2020, 4:25 p.m.

alguien e puede explicar esto