| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 104 | 11 | 9 | 50.000% |
여러분은 광산에서 광물을 수집하고 가공하여 회사에 납품하는 일을 하고 있다. 일하는 광산은 반직선의 형태로 되어 있다. 광산에는 매일 아침 $N$개의 종류의 광물이 생성된다. 이때, $i$번 광물은 수직선 $x_i$ 위치에 $y_i$개 생성된다. $(1 \le i \le N)$
회사로부터 받은 특이한 로봇 하나를 원격 조작하여 광물을 채취하고 가공하려고 한다. 이 로봇의 특징은 다음과 같다.
여러분은 일과는 광산에 존재하는 모든 광물을 소모하여 보석을 만들고 로봇을 처음 위치로 돌려놓는 것이다. 똑똑한 여러분은 하루에 일과를 끝낼 수 있는 최소한의 에너지 $E$만큼만 사용하여 로봇을 조종해 보석을 만든다. 당일 일과를 무사히 마쳤다면 다음 날에는 당일 아침과 같은 상태로 복원된다.
회사에서 매일 VIP의 요구 사항 $1$개를 전달받는다. $k$일차 요구 사항은 양의 정수 $a_k$, $b_k$로 구성되어 있다. 이는 $a_k$번 광물과 $b_k$번 광물을 포함한 보석을 요구함을 의미한다. $(1 \le k \le Q)$
$k$일차 요구 사항을 받았을 때, $E$만큼의 에너지를 사용하여 여러분의 일과를 무사히 마치면서 $a_k, b_k \in S_j$를 만족하는 보석 $j$를 만들 수 있는지 판단하는 프로그램을 작성하시오.
첫 번째 줄에 광물의 종류 $N$, 로봇 저장소에 담을 수 있는 광물의 최대 수 $M$, 근무 기간 $Q$가 공백으로 구분되어 주어진다. $(2 \le N, M \le 200\,000;$ $1 \le Q \le 200\,000)$
두 번째 줄에는 $N$개의 줄에 걸쳐 광물의 정보가 주어진다. 그중 $i$번째 줄에는 $i$번 광물의 위치 $x_i$, 광물의 개수 $y_i$가 공백으로 구분되어 주어진다. 주어지는 광물의 위치는 서로 다르다. $(1 \le x_i, y_i \le 10^9)$
그다음 줄부터 $Q$개의 줄에 걸쳐 VIP 고객의 요구 사항이 주어진다. 그중 $k$번째 줄에는 서로 다른 두 개의 광물 $a_k$와 $b_k$가 공백으로 구분되어 주어진다. $(1 \le a_k, b_k \le N;$ $a_k \neq b_k)$
$Q$개의 줄에 걸쳐 VIP 고객의 요구 사항을 만족하는 보석을 만들 수 있다면 YES, 없다면 NO를 출력한다.
4 2 2 1 1 2 2 3 1 4 2 1 3 3 4
YES NO
해당 예제에서 일과를 끝낼 수 있는 최소 에너지 $E$는 $18$이다.
첫째 날에 로봇을 위치 $4$로 이동하여 네 번째 광물을 두 개 수집 후 원점으로 이동 후 보석 제조, 위치 $2$로 이동하여 두 번째 광물을 두 개 수집 후 원점으로 이동하여 보석 제조, 위치 $3$으로 이동하여 세 번째 광물을 하나, 위치 $1$로 이동하여 첫 번째 광물을 하나 수집한 후 원점으로 돌아와 보석을 제조하면 최소 에너지 $18$을 만족하며 VIP가 원하는 보석을 제조할 수 있다.
둘째 날은 로봇을 어떻게 조작하여도 세 번째 광물과 네 번째 광물을 동시에 담아오면서 에너지를 $18$보다 작거나 같게 소모하는 것이 불가능하기 때문에 NO를 출력하고 일과를 무사히 마칠 수 있는 방법을 택한다.
5 3 5 1 2 2 3 10 1 8 1 15 2 3 5 4 5 1 4 1 2 2 3
YES NO YES YES NO