Rectángulo más Largo

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 128M

Author:

Problem type

Allowed languages

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

El ogro Ork está planeando demoler un número de viejos edificios desocupados y construir un centro comercial en su lugar. Para ello necesita que Usted encuentre la mayor área sólida en la que se pueda construir el centro comercial. Los edificios que se elijan para construir el centro comercial tienen que ser consecutivos.

Se tienen $n(1 \le n \le 10^5)$ ~n(1 \le n \le 10^5)~ edificios, cada uno de ellos tiene una altura $h(1 \le h \le 10^6)$ ~h(1 \le h \le 10^6)~. Si se unen $k$ ~k~ edificios adyacentes partiendo del edificio $i$ ~i~ se forma un rectángulo sólido de área $k * min (h_{i}, h_{i+1}, \dots , h_{i+k-1})$ .

Por ejemplo si se eligen tres edificios consecutivos con altura $[3, 2, 3]$ ~[3, 2, 3]~ se crea un área sólida con altura $h = 2$ ~h = 2~ y longitud $k = 3$ ~k = 3~, el valor del área es $k*h = 3 * 2 = 6$ ~k*h = 3 * 2 = 6~.

Entrada

La primera línea contiene un número entero $n$ ~n~, la cantidad de edificios.

La segunda línea contiene $n$ ~n~ enteros separados por espacios en blanco, cada uno representa la altura de un edificio.

Salida

La primera y única línea de salida contiene un número entero, el área del mayor rectángulo formado.

Ejemplo de Entrada

5
1 2 3 4 5

Ejemplo de Salida

Explicación del Ejemplo

Se eligen tres edificios a partir del tercero $[3, 4, 5]$ ~[3, 4, 5]~, la longitud es $k = 3$ ~k = 3~, luego el área es $k * min (3, 4, 5) = 3 * 3 = 9$ ~ k * min (3, 4, 5) = 3 * 3 = 9~.

Comments

1

Samuel08DA commented on March 5, 2023, 6:35 p.m.

Necesito ayuda en el problema de multiplicación en rango, q alguien me ayude

1

josue commented on March 14, 2020, 5:41 p.m.

hacer dos bucles da AC porque los casos de prueba estan flojos.Esa solución es O(n^2).si pruebas un caso con los números desde 1 hasta 10^5 en orden,tardarias aproximadamente 100 segundos.

-4

Primervirgen commented on March 14, 2020, 4:39 p.m.

Una solucion bastante óptima es simplemente buscar para cada posición 'i' hasta q posición 'r' (r>i) se extiende el área y luego para 'l' (l<i). D esa forma con q aumentes un contador en 1 mientras buscas esos límites mediante 2 bucles o una Búsqueda Binaria, al final dices: sol = max(sol, cont*arr[i])

3

aniervs commented on March 14, 2020, 5:46 p.m.

una cosa es óptima o no lo es, no puede ser bastante óptima, decir eso es lo mismo que decir más mejor.

0

josue commented on March 14, 2020, 4:08 p.m.

yo aquí hablando de O(n) y la sengunda solucion mas rapida es O(n^2) tremendos casos de prueba

4

josue commented on March 12, 2020, 2:07 p.m.

hay una solución en O(n).en vez de computar los extremos de los rangos con sparse table o segment tres lo haces con una pila

1

aniervs commented on March 13, 2020, 4:42 p.m.

Cierto

-3

Alejandro777 commented on March 10, 2020, 7:21 p.m.

alguien me puede ayudar con este trouble?

5

aniervs commented on March 11, 2020, 11:04 p.m.

Solución en $O(n\cdot \log n)$ ~O(n\cdot \log n)~: para cada posición vamos a computar el rectángulo de máxima área cuya altura sea igual a la altura de esa posición. Para hacer eso, basta con buscar para la posición $i$ ~i~ la menor posición $r>i: h_r<h_i$ ~r>i: h_r<h_i~ y la mayor posición $l<i: h_l<h_i$ ~l<i: h_l<h_i~, entonces el mayor rectángulo de altura $h_i$ ~h_i~ que contiene a $i$ ~i~ tiene área $A_i=h_i\cdot (r-l-1)$ ~A_i=h_i\cdot (r-l-1)~, para computar $r$ ~r~ y $l$ ~l~ podemos hacer búsqueda binaria con alguna estructura de datos que compute mínimo en rangos como Sparse Table. La solución sería el $\max_{1\le i \le n} {A_i}$ ~\max_{1\le i \le n} {A_i}~.