산책로 1초 128MB
문제
정부는 참나무 숲 한가운데에 관광객들을 위한 산책로를 건설할 계획입니다.
숲에는 N 그루의 참나무가 있고, 해당 참나무들의 위치는 평면 위에서의 격자점으로 나타낼 수 있습니다.
산책로는 측면이 축과 평행한 직사각형으로 이루어집니다.
산책로를 이루는 직사각형의 측면이 참나무의 위치와 교차하는 경우, 이러한 나무는 베어야 합니다.
직사각형 안에 있는 나무는 자를 필요가 없습니다.
산림청 장관은 관광부 장관에게 관광객을 끌어들일 만큼 매력적인 직사각형 산책로 목록을 제공하라고 지시했습니다.
산림청 장관은 열정적인 자연 애호가이기 때문에 가장 적은 양의 참나무가 베어져야 하는 산책로를 선택할 계획입니다.
목록으로 주어진 산책로들에 대해서 각 산책로마다 최소로 베어야하는 참나무의 수를 출력하는 프로그램을 작성합시다.
입력
첫 번째 줄에 나무의 수를 뜻하는 정수 N 이 입력된다 (1 ≤ N ≤ 300,000)
다음 N 줄에 나무의 좌표 Xi Yi가 입력된다. 각 격자점에는 최대 하나의 나무만 있다 (1 ≤ X, Y ≤ 109)
다음 줄에는 보행로 수를 뜻하는 정수 P가 입력된다 (1 ≤ P ≤ 100,000)
다음 P 줄에 직사각형의 왼쪽 하단(X1, Y1)과 오른쪽 상단(X2, Y2) 모서리 좌표를 뜻하는 정수 X1, Y1, X2, Y2가 입력된다 (1 ≤ X1 < X2 ≤ 109, 1 ≤ Y1 < Y2 ≤ 109)
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 10점 | N <= 100 |
| #2 | 90점 | 추가 제한 없음 (부분 점수 가능) |
예제
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
로그인해야 코드를 작성할 수 있어요.