시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 70 20 7 77.778%

문제

정부는 오크 나무 숲을 통과하는 산책길를 만드려고 한다. 숲을 평면으로 나타낼 수 있고, 나무 N개는 평면위의 격자점으로 나타낼 수 있다.

산책길는 축에 평행한 직사각형으로 나타낸다. 산책길의 변 위에 있는 나무는 베어내야 한다. 산책길 내부에 있는 나무는 문제가 되지 않으며, 베어내지 않아도 된다.

산림청에서는 산책길 계획을 공모전으로 열었고, 총 P개의 산책길가 접수되었다. 각각의 접수된 산책길에 대해서, 그 산책길를 만드려면 나무를 몇 개나 잘라내야하는지 구하는 프로그램을 작성하시오. 나무는 변 위에 있는 나무만 베어야한다.

입력

첫째 줄에 나무의 수 N이 주어진다. (1 ≤ N ≤ 300,000)

다음 N개 줄에는 나무의 좌표 X와 Y가 한 줄에 하나씩 주어진다. 한 점위에 나무가 두 개 이상 있는 경우는 없다. (1 ≤ X, Y ≤ 109)

다음 줄에는 접수된 산책로 계획의 수 P (1 ≤ P ≤ 100,000)가 주어진다.

다음 P개 줄에는 X1, Y1, X2, Y2 (1 ≤ X1 < X2 ≤ 109, 1 ≤ Y1 < Y2 ≤ 109)가 주어진다. (X1, Y1)은 직사각형의 왼쪽 아래 좌표, (X2, Y2)는 오른쪽 위 좌표를 나타낸다.

출력

총 P개의 줄에 각 산책로를 건설하려면 나무를 몇 개나 베어야 하는지 출력한다. 입력으로 주어진 순서를 지켜 출력한다.

예제 입력

6
1 2
3 2
2 3
2 5
4 4
6 3
4
2 2 4 4
2 2 6 5
3 3 5 6
5 1 6 6

예제 출력

3
4
0
1

힌트

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2010 > Croatian Olympiad in Informatics 2010 1번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: songuno1