시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 101 | 43 | 35 | 40.698% |
1번부터 $N$번까지의 번호가 붙어있는 $N$개의 안테나가 일렬로 놓여 있다. 각 안테나는 다른 연속된 안테나와 1km 떨어져 있다. $i$번 ($1 \le i \le N$) 안테나의 높이는 $H_i$이다. $i$번 안테나는 자신으로 부터 $A_i$km 이상 $B_i$km 이하 떨어져 있는 안테나에게만 정보를 보낼 수 있다. 만약 $x$번 안테나와 $y$번 안테나가 ($1 \le x < y \le N$) 서로 정보를 주고 받을 수 있다면, 이 둘은 통신할 수 있고, 통신 비용은 $|H_x - H_y|$이다.
JOI 공화국의 수상 K씨는 시민들로부터 연결상태에 관한 불만 $Q$개를 들었다. 조사 결과 $j$ 번째 ($1 \le j \le Q$) 불만은, $L_j, \ L_j +1, \cdots, R_j$번 안테나 중 무언가가 이상이 있는것으로 밝혀졌다. 당신은, 이 안테나들중 서로 통신할 수 있는 안테나 쌍이 있는지, 만약 있다면 그 중 가장 통신 비용이 높은 쌍의 통신 비용은 얼마인지 알아보는 일을 맡았다.
안테나의 정보와 불만의 정보가 주어졌을 때, $L_j, \ L_j +1, \cdots, R_j$번 안테나 중 서로 통신할 수 있는 쌍이 있는지, 있다면 통신 비용의 최댓값은 얼마인지를 알려주는 프로그램을 작성하여라.
표준 입력에서 다음과 같은 형식으로 주어진다. 모든 값은 정수이다.
$N$
$H_1$ $A_1$ $B_1$
$\vdots$
$H_N$ $A_N$ $B_N$
$Q$
$L_1$ $R_1$
$\vdots$
$L_Q$ $R_Q$
표준 출력으로 $Q$개의 줄을 출력하여라. $j$번째 ($1 \le j \le Q$)줄은 $L_j, \ L_j +1, \cdots, R_j$번 안테나 중 서로 통신할 수 있는 쌍이 없으면 -1
, 있다면 통신 비용의 최댓값이어야 한다.
번호 | 배점 | 제한 |
---|---|---|
1 | 2 | N ≤ 300, Q ≤ 300. |
2 | 11 | N ≤ 2 000. |
3 | 22 | Q = 1, L1 = 1, R1 = N. |
4 | 65 | No additional constraints. |
5 10 2 4 1 1 1 2 1 3 1 1 1 100 1 1 5 1 2 2 3 1 3 1 4 1 5
-1 1 8 8 99
1번 안테나와 2번 안테나는 서로 통신할 수 없으므로, 첫 번째 불만에 대한 답은 -1이다.
두 번째, 세 번째, 네 번째, 다섯 번째 불만에 대한 최대 통신 비용을 가진 안테나 쌍은 각각 (2, 3), (1, 3), (1, 3), (4, 5) 이다.
20 260055884 2 15 737689751 5 5 575359903 1 15 341907415 14 14 162026576 9 19 55126745 10 19 95712405 11 14 416027186 8 13 370819848 11 14 629309664 4 13 822713895 5 15 390716905 13 17 577166133 8 19 195931195 10 17 377030463 14 17 968486685 11 19 963040581 4 10 566835557 1 12 586336111 6 16 385865831 8 9 1 1 20
806460109
Camp > JOI Spring Training Camp > JOI 2018/2019 Spring Training Camp 2-1번