문제
좌표평면 상에 N개의 점이 있다.
i번 점의 좌표는 (Xi, Yi)이다.
점들을 간선으로 연결할 것이다.
각 점에 대하여,
- 자신보다 X좌표와 Y좌표가 모두 작은 점 최대 1개
- 자신보다 X좌표와 Y좌표가 모두 큰 점 최대 1개
최대 총 2개의 점과 연결할 수 있다.
이렇게 연결된 점들은 여러 개의 연결된 덩어리(컴포넌트)를 이룬다.
Q개의 쿼리 (Aj, Bj)가 주어진다.
각 쿼리마다, Xi ≥ Aj>이고 Yi ≤ Bj인 점들만이 존재한다고 가정하여, 점들을 조건에 따라 연결하였을 때 만들 수 있는 덩어리의 최소 개수를 구하여라.
입력
1번 줄 : N Q
2번 ~ N + 1번 줄 : Xi Yi
N + 2 ~ N + Q + 1번 줄 : Aj Bj
1 ≤ N, Q ≤ 200 000
1 ≤ Xi, Yi, Aj, Bj ≤ 1 000 000 000
출력
Q개의 줄에 걸쳐 j번 줄에 j번 쿼리의 결과를 출력하여라.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 11점 | N ≤ 10, Q = 1 |
| #2 | 15점 | N ≤ 100, Q = 1 |
| #3 | 25점 | N ≤ 2 000, Q ≤ 2 000 |
| #4 | 49점 | 문제의 조건 외에 주어진 제한이 없다. |
예제 #1
7 3
9 5
3 7
10 6
5 10
2 6
10 10
4 1
10 5
3 5
3 9
0
1
2
3번 쿼리의 경우, X좌표가 3 이상, Y좌표가 9 이하인 점들만을 사용한다.
1번, 2번, 3번, 7번 점을 사용한다.
7번 - 1번 - 3번 점, 2번 점으로 연결할 경우 컴포넌트가 2개이다.
예제 #2
10 8
14 19
9 16
11 2
7 18
20 16
9 5
10 9
20 6
4 17
13 8
7 14
9 3
9 13
4 19
12 4
19 16
18 10
7 14
3
1
3
5
0
2
1
3
힌트
출처
JOISC 2016 Day 1
로그인해야 코드를 작성할 수 있어요.