Rectangular Pasture.
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 vacas ocupando algunas de esas celdas .
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 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 . Cada una de las siguientes líneas contiene dos enteros separados por espacio, indicando las coordenadas de la celda de una vaca. Todas las coordenadas son distintas de las otros, y todas las coordenadas son distintas de las otras. Todos los valores de y de están en el rango .
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
4
0 2
1 0
2 3
3 5
Ejemplo de Salida
13
Explicación
Hay en total 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
Los casos de prueba 4-6 satisfacen
Los casos de prueba 7-12 satisfacen
Los casos de prueba 13-20 no satisfacen restricciones adicionales.
Comments