아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

허수아비

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

요약
남서쪽과 북동쪽 모서리에 허수아비가 있고 내부에 다른 허수아비가 없는 축에 평행한 직사각형의 개수를 센다.
난이도

어려움10점 중 8점

유형
정렬, 분할 정복, 세그먼트 트리
정답자
아직 제출이 없습니다

문제

JOI 마을의 넓은 황무지에는 허수아비 N개가 서 있고, 마을 사람들은 일 년에 몇 번씩 허수아비를 둘러싸고 축제를 열었다. 어느 날, 허수아비의 계시를 들었다는 JOI 마을의 촌장은 황무지에 밭을 하나 만들 계획을 세웠다. 계시에 따르면 밭은 다음 조건을 만족해야 한다.

  • 각 변이 동서 방향 또는 남북 방향인 직사각형이다.
  • 남서쪽 꼭짓점과 북동쪽 꼭짓점에 허수아비가 서 있다.
  • 밭의 내부(경계 제외)에는 허수아비가 서 있지 않다.

물론 소중한 허수아비를 옮기는 것은 허용되지 않는다. 계시를 따르는 밭의 위치는 몇 개인가?

허수아비의 위치가 주어졌을 때, 계시를 따르는 밭의 위치의 개수를 구하는 프로그램을 작성하라.

입력

표준 입력에서 다음 데이터를 읽는다.

  • 첫째 줄에는 정수 N이 쓰여 있으며, 허수아비가 N개 서 있음을 나타낸다.
  • 이어지는 N개 줄 중 i번째 줄(1 ≤ i ≤ N)에는 정수 Xi, Yi가 공백을 구분으로 쓰여 있다. JOI 마을의 황무지는 xy 좌표 평면으로 나타내며, x축 양의 방향이 동쪽 방향, y축 양의 방향이 북쪽 방향이다. i번째 허수아비는 좌표 (Xi, Yi)에 서 있다.

출력

표준 출력에 계시를 따르는 밭의 위치의 개수를 한 줄로 출력하라.

제한

  • 1 ≤ N ≤ 200 000.
  • 0 ≤ Xi ≤ 1 000 000 000 (1 ≤ i ≤ N).
  • 0 ≤ Yi ≤ 1 000 000 000 (1 ≤ i ≤ N).
  • Xi (1 ≤ i ≤ N)는 서로 다르다.
  • Yi (1 ≤ i ≤ N)는 서로 다르다.

예제2

  1. 예제 1

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

    입력
    10
    2 1
    3 0
    6 3
    10 2
    16 4
    0 8
    8 12
    11 14
    14 11
    18 10
    
    예상 출력
    15