문제
당신은 마트료시카 인형을 판매하는 가게를 열기로 했다. 당신은 N개의 마트료시카 인형을 공장에 주문했다. 여기에는 1부터 N까지의 번호가 붙어 있었다. 그 중 i번째(1 ≤ i ≤ N) 마트료시카 인형은 바닥의 지름이 Ricm, 높이가 Hi cm인 속이 빈 원기둥으로 생각 할 수 있다. 마트료시카 인형은 중첩해서 안에 넣을 수 있다. 각각의 마트료시카 인형은, 자신보다 지름과 높이가 모두 작은 마트료시카 인형을 1개까지만 안에 넣을 수 있다. 수납된 마트료시카 인형 안에 다른 인형을 넣을 수도 있다.
어느 날, 마트료시카 인형을 주문한 공장에서 연락이 왔다. 주문한 N개의 마트료시카 인형을 모두 한번에 준비 할 수 없어서, N개의 마트료시카 인형 중 바닥의 직경이 A cm 이상, 높이 B cm 이하의 마트료시카만 모두 사전에 보내준다고 한다. A와 B는 갑자기 변할지도 모른다. 그래서 당신은, Q개의 쌍 (Aj , Bj ) (1 ≤ j ≤ Q) 각각에 대해, 사전에 도착하는 마트료시카 인형을 중첩해서 넣었을 때, 어떤 마트료시카 인형에도 들어가지 못하는 인형의 갯수의 최솟값을 구하기로 하였다.
각각의 마트료시카 인형의 바닥의 지름과 높이에 대한 정보와, Q개의 쌍 (Aj , Bj ) (1 ≤ j ≤ Q)이 주어진다.
각각의 쌍에 대해서, 사전에 도착하는 마트료시카 인형을 중첩해서 넣을 때, 어떤 마트료시카 인형에도 들어가지 못하는 마트료시카 인형의 갯수의 최솟값을 구하는 프로그램을 작성하여라.
• 1 ≤ N ≤ 200 000
• 1 ≤ Q ≤ 200 000
• 1 ≤ Ri ≤ 1 000 000 000 (1 ≤ i ≤ N)
• 1 ≤ Hi ≤ 1 000 000 000 (1 ≤ i ≤ N)
• 1 ≤ Aj ≤ 1 000 000 000 (1 ≤ j ≤ Q)
• 1 ≤ Bj ≤ 1 000 000 000 (1 ≤ j ≤ Q)
입력
첫째 줄에는, 정수 N, Q가 공백으로 구분되어 들어온다. 이것은, 주문한 마트료시카 인형이 N개이고, (A, B)쌍의 수가 Q개라는 것을 의미한다.
다음 N개의 줄의 i번째 줄(1 ≤ i ≤ N)에는, 정수 Ri , Hi가 공백으로 구분되어 들어온다. 이것은, i번째 마트료시카 인형은, 바닥의 지름이 Ricm 이고, 높이가 Hicm 임을 의미한다.
다음 Q개의 줄의 j번째 줄(1 ≤ j ≤ Q)에는, 정수 Aj , Bj가 공백으로 구분되어 들어온다.
출력
출력은 Q개의 줄로 한다. j번째 줄(1 ≤ j ≤ Q)에는, 쌍 (Aj , Bj ) 에 대해, 사전에 도착한 마트료시카 인형을 중첩해서 넣을 때, 어떤 마트료시카 인형에도 들어가지 못하는 마트료시카 인형의 갯수의 최솟값을 출력하여라.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #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
예제 #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
로그인해야 코드를 작성할 수 있어요.