Submit solution


Points: 100 (partial)
Time limit: 4.0s
Java 8 6.0s
Python 12.0s
Memory limit: 1G
Java 8 1G
Python 1G

Author:
Problem type
Allowed languages
C, C++, Java, Python

Esta noche, en tu cine favorito están dando la película Joker y todos los asientos están ocupados. En el cine hay \(N\) filas con \(N\) asientos cada una, formando un cuadrado \(N × N\). Denotamos con \(1,2,…, N\) los espectadores en la primera fila (de izquierda a derecha); con \(N + 1,…, 2\cdot N\) los espectadores en la segunda fila (de izquierda a derecha); y así sucesivamente hasta la última fila, cuyos espectadores se indican con \(N^2 − N + 1,…, N^2\).

Al final de la película, los espectadores salen del cine en un orden determinado: el i -ésimo espectador que abandona su asiento es el que se indica con el número \(P_i\). El espectador \(P_{i + 1}\) espera hasta que el espectador \(P_i\) haya abandonado el cine antes de dejar su asiento. Para salir del cine, un espectador debe moverse de un asiento a otro hasta que salga de la plaza de asientos (cualquier lado de la plaza es una salida válida). Un espectador puede moverse de un asiento a uno de sus 4 asientos adyacentes (misma fila o misma columna). Al salir del cine, puede ser que cierto espectador \(x\) pase por un asiento actualmente ocupado por el espectador \(y\); en ese caso, el espectador \(y\) odiará al espectador \(x\) para siempre. Cada espectador elige la forma que minimiza la cantidad de espectadores que lo odiarán para siempre.

Calcule la cantidad de pares de espectadores \((x, y)\) tal que \(y\) odiará \(x\) para siempre.

Restricciones
  • \(2 ≤ N ≤ 500\)

  • La secuencia \(P_1, P_2,…, P_{N^2}\) es una permutación de \({1,2,…, N^2}\).

Entrada

La entrada se da desde entrada estándar en el formato

n
p1, p2, ..., pn^2
Salida

Si ans es el número de pares de visores descritos en la declaración, debe imprimir en salida estándar

ans
Puntuación

En al menos 55% de los casos se tiene que \(n \leq 100\).

Ejemplo de entrada 1:
3
1 3 7 9 5 4 8 6 2
Ejemplo de salida 1:
1

Antes del final de la película, los espectadores se organizan en el cine de la siguiente manera:

1 2 3
4 5 6
7 8 9

Los primeros cuatro espectadores que abandonan el cine \((1, 3, 7, 9)\) pueden salir del cine sin pasar por ningún asiento, para que nadie los odie.

Entonces, espectador \(5\) debe pasar por uno de los asientos donde los espectadores \(2, 4, 6, 8\) actualmente están sentados al salir del cine; por lo tanto, al menos uno de esos espectadores lo odiará.

Finalmente los espectadores restantes pueden salir del cine (en el orden \(4 , 8, 6, 2\)) sin pasar por ningún asiento ocupado (en realidad, pueden salir del cine sin pasar por ningún asiento).

Ejemplo de entrada 2:
4
6 7 1 4 13 16 10 9 5 11 12 14 15 2 3 8
Ejemplo de salida 2:
3
Ejemplo de entrada 3:
6
11 21 35 22 7 36 27 34 8 20 15 13 16 1 24 3 2 17 26 9 18 32 31 23 19 14 4 25 10 29 28 33 12 6 5 30
Ejemplo de salida 3:
11

Comments

There are no comments at the moment.