Rectangular Pasture.


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 128M

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

El mayor pastizal del Granjero Juan puede ser representando como una cuadrícula 2D de "celdas" cuadradas (imagine un tablero de ajedrez enorme). Actualmente, hay N vacas ocupando algunas de esas celdas (1N2500).

El Granjero Juan quiere construir una cerca que encerrará una región rectangular de celdas; el rectángulo debe estar orientado de manera que sus lados sean paralelos a los ejes xy y, y podría ser tan pequeño como una sola celda. Por favor ayúdelo a contar el número de distintos subconjuntos de vacas que puede encerrar en una de tales regiones. Note que el conjunto vacio puede ser contado como uno de ellos.

Entrada

La primera línea contiene un solo entero N. Cada una de las siguientes N líneas contiene dos enteros separados por espacio, indicando las coordenadas (x,y) de la celda de una vaca. Todas las coordenadas x son distintas de las otros, y todas las coordenadas y son distintas de las otras. Todos los valores de x y de y están en el rango 0...109.

Salida

El número de subconjutos de vacas que GJ puede cercar. Se puede demostrar que esta cantidad entrará en un entero de 64 bits con signo (esto es un "long long" en C/C++).

Ejemplo de Entrada

Copy
4
0 2
1 0
2 3
3 5

Ejemplo de Salida

Copy
13

Explicación

Hay en total 24 subconjuntos. FJ no puede crear un cerco encerrando solamente a las vacas 1, 2, y 4, o solamente a las vacas 2 y 4, o solamente a las vacas 1 y 4, entonces la respuesta es 24 - 3 = 16 - 3 = 13.

Calificación

Los casos de prueba 2-3 satisfacen N20

Los casos de prueba 4-6 satisfacen N100

Los casos de prueba 7-12 satisfacen N500

Los casos de prueba 13-20 no satisfacen restricciones adicionales.


Comments

There are no comments at the moment.