Castillo de arena


Submit solution

Points: 100 (partial)
Time limit: 4.0s
Memory limit: 512M

Authors:
Problem type
Allowed languages
C++, Python

Descripción

OCI-Cub está jugando en una playa de arena. Hace un castillo de arena. El castillo de arena hecho por OCI-Cubo está contenido en una región rectangular en la playa de arena. La región rectangular consta de celdas de H filas horizontales y W columnas verticales. La celda en la fila i-ésima (1 \le i \le H) desde el norte y la columna j-ésima (1 \le j \le W) desde el oeste tiene altura A_{i, j}. Obsérvese que los valores de A_{i, j} son diferentes entre sí.

Para el castillo de arena, OCI-Cub realizó las siguientes acciones.

  1. En primer lugar, OCI-Cub eligió una celda, y comenzó a moverse desde la celda elegida.

  2. A continuación, se movió desde la celda actual a una celda adyacente en una de las cuatro direcciones. Tiene que moverse a una celda que esté más abajo que la celda actual. Repitió esto cero o más veces.

Por último, si vemos las celdas que ha visitado desde arriba, las celdas forman un rectángulo.

Tarea

Dada la información de la altura A_{i, j} de cada celda, escribe un programa que calcule el número de rectángulos posibles formados por las celdas visitadas por OCI-Cub.

Entrada

Lea los siguientes datos de la entrada estándar. Los valores dados son todos enteros.

H W

A_{1,1} A_{1,2} --- A_{1,W}

A_{2,1} A_{2,2} --- A_{2,W}

.

.

.

A_{H,1} A_{H,2} --- A_{H,W}~

Salida

Escriba una línea en la salida estándar. La salida debe contener el número de posibles rectángulos formados por las celdas visitadas por OCI-Cub.

Restricciones

  • H \ge 1.
  • W \ge 1.
  • H × W \le 50 000.
  • 1 \le A_{i, j} \le 10 000 000 (1 \le i \le H, 1 \le j = W).
  • A_{i1, j1}A_{i2, j2} (1 \le i_1 \le H, 1 \le j_1 \le W, 1 \le i_2 \le H, 1 \le j_2 \le W, (i_1, j_1)(i_2, j_2)).

Subtareas

  1. (9 puntos) H = 1.
  2. (10 puntos) H × W \le 100.
  3. (5 puntos) H × W \le 1 500.
  4. (56 puntos) H × W \le 7 000.
  5. (20 puntos) Sin restricciones adicionales.
Ejemplo de entrada y salida

Ejemplo de Entrada #1

1 5
2 4 7 1 5

Ejemplo de Salida #1

10

Dado que hay 10 rectángulos posibles formados por las celdas visitadas por OCI-Cub, salida 10

Este ejemplo de entrada satisface las restricciones de todas las subtareas.

Ejemplo de Entrada #2

3 2
18 10
19 12
17 13

Ejemplo de Salida #2

15

Como hay 15 rectángulos posibles formados por las celdas visitadas por JOI-kun, salida 15

Esta entrada de ejemplo satisface las restricciones de las subtareas 2, 3, 4, 5.

Ejemplo de Entrada #3

3 5
83 47 36 38 40
13 10 26 68 67
15 19 20 70 90

Ejemplo de Salida #3

65

Por ejemplo, los siguientes rectángulos pueden estar formados por las celdas visitadas por OCI-Cub. Como hay 65 rectángulos posibles en total, salida 65.

Este ejemplo de entrada satisface las restricciones de las subtareas 2, 3, 4, 5.


Comments


  • 0
    leocar  commented on June 6, 2023, 2:56 p.m.

    Reenviar la solución error en caso de pruebas de la primera subtarea