만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

세 점

시간 제한2초메모리 제한512 MB

요약
x 좌표가 증가하고 y 좌표가 r < b < g 순서가 되는 세 점의 조합 수를 센다.
난이도

보통10점 중 7점

유형
정렬, 누적 합, 조합론
정답자
아직 제출이 없습니다

문제

무한히 넓은 이차원 평면에 점이 N개 있다. 점의 번호는 0번부터 N-1번까지이고, i번 점의 좌표는 (xi,yi)(x_i, y_i)이다. 서로 다른 두 점이 같은 x좌표를 갖는 경우는 없고, 같은 y좌표를 갖는 경우도 없다.

이 중에서 세 점을 골라 각각 빨간색, 초록색, 파란색으로 칠한다. 빨간색으로 칠한 점의 번호를 rr, 초록색으로 칠한 점의 번호를 gg, 파란색으로 칠한 점의 번호를 bb라고 하자. 색칠은 xr<xg<xbx_r < x_g < x_b와 yr<yb<ygy_r < y_b < y_g를 동시에 만족해야 한다.

점의 좌표가 주어졌을 때, 조건을 만족하도록 세 점을 색칠하는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄부터 N개의 줄에 점의 좌표 xx와 yy가 공백을 사이에 두고 하나씩 주어진다. (1≤N≤300,0001 \le N \le 300{,}000, 0≤x,y<1,000,000,0000 \le x, y < 1{,}000{,}000{,}000)

출력

첫째 줄에 조건을 만족하도록 세 점을 색칠하는 방법의 수를 출력한다. 이 값은 32비트 정수의 범위를 넘을 수 있다.

예제5

  1. 예제 1

    입력
    9
    3 5
    8 10
    4 1
    5 4
    2 3
    0 7
    6 2
    10 0
    9 8
    
    예상 출력
    8
    
  2. 예제 2

    입력
    1
    5 7
    
    예상 출력
    0
    
  3. 예제 3

    입력
    2
    0 1
    1 0
    
    예상 출력
    0
    
  4. 예제 4

    입력
    3
    0 0
    1 2
    2 1
    
    예상 출력
    1
    
  5. 예제 5

    입력
    3
    0 0
    1 1
    2 2
    
    예상 출력
    0