| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 20 | 14 | 11 | 91.667% |
UDPC 나라의 통신 설비를 담당하는 윤이는 직선 도로를 따라 $N$개의 송신탑을 설치하려고 한다.
윤이의 역할은 송신탑 사이에 전파 간섭이 일어나지 않도록 송신탑의 위치와 전파 우선순위를 설정하는 일이다. 송신탑에는 $1$번부터 $N$번까지 번호가 붙어 있으며, 번호 순서대로 왼쪽에서 오른쪽으로 설치해야 한다. $1$번 송신탑의 좌표는 $0$으로 고정한다. 송신탑의 전파 우선순위로는 $1$ 이상 $N$ 이하의 서로 다른 정수를 배정해야 한다.
송신탑이 전파 간섭을 일으키는 상황은 다음과 같다. $i$번 송신탑이 설치된 좌표를 $x_i$라고 하면, 전파 간섭을 일으킬 수 있는 범위는 $(x_i-L_i, x_i+R_i)$ 구간이다. 구간의 양 끝은 간섭 범위에 포함되지 않는다. $i$번 송신탑의 전파 우선순위를 $p_i$라고 할 때, $i$번 송신탑의 간섭 범위 안에 $p_i < p_j$인 $j$번 송신탑이 존재하면 전파 간섭이 발생한다.
윤이는 각 송신탑의 위치와 전파 우선순위를 적절히 설정하여 $1$번 송신탑과 $N$번 송신탑 사이의 거리를 최소화하려고 한다. 조건을 만족하도록 송신탑을 설치하는 방법을 찾으시오.
첫째 줄에 송신탑의 개수 $N$이 주어진다. $(1 \le N \le 300\,000)$
다음 $N$개 줄의 $i$번째 줄에는 $i$번 송신탑의 간섭 범위를 나타내는 정수 $L_i$, $R_i$가 공백으로 구분되어 주어진다. $(1 \le L_i, R_i \le 10^9)$
총 $N$개의 줄을 출력한다. $i$번째 줄에는 $i$번 송신탑의 좌표와 전파 우선순위를 공백으로 구분하여 출력한다.
가능한 답이 여러 가지이면 하나만 출력한다.
4 1 5 3 4 10 2 4 2
0 2 3 1 7 3 9 4
6 3 10 1 2 1 1 5 2 8 1 2 1
0 6 1 2 2 1 5 3 8 4 9 5