가장 밝은 등불
골드 III의견: 0
축제의 밤하늘에 \(N\)개의 등불이 떠 있다. \(i\)번째 등불의 밝기는 \(B_i\)이고, 지금으로부터 \(D_i\)분 뒤에 불이 꺼져 사라진다. 한 번 꺼진 등불은 다시 켜지지 않는다.
등불은 꺼지는 시각이 빠른 순서대로 번호가 매겨져 있다. 즉 \(D_1 \le D_2 \le \dots \le D_N\)이 성립한다.
\(Q\)개의 질문이 주어지니 순서대로 답하라. \(i\)번째 질문에서는 정수 \(T_i\)가 주어진다. 지금으로부터 \(T_i + \frac{1}{2}\)분 뒤에 아직 켜져 있는 등불들 중에서 가장 밝은 등불의 밝기를 구하면 된다.
이 문제의 제약 조건에서, \(T_i + \frac{1}{2}\)분 뒤에 켜져 있는 등불이 적어도 하나 존재함이 보장된다.
- \(1 \le N \le 3 \times 10^5\)
- \(1 \le B_i \le 10^9 \ (1 \le i \le N)\)
- \(1 \le D_1 \le D_2 \le \dots \le D_N \le 10^9\)
- \(1 \le Q \le 3 \times 10^5\)
- \(0 \le T_i < D_N \ (1 \le i \le Q)\)
- 입력으로 주어지는 모든 값은 정수이다.
첫째 줄에 정수 \(N\)이 주어진다.
이어지는 \(N\)개의 줄 중 \(i\)번째 줄에는 두 정수 \(B_i\)와 \(D_i\)가 공백으로 구분되어 주어진다.
그다음 줄에 정수 \(Q\)가 주어진다.
마지막 줄에 \(Q\)개의 정수 \(T_1, T_2, \dots, T_Q\)가 공백으로 구분되어 주어진다.
\(Q\)개의 줄을 출력한다. \(i\)번째 \((1 \le i \le Q)\) 줄에는 \(i\)번째 질문에 대한 답을 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 30점 | \(N, Q \le 2000\) |
Subtask 2 | 20점 | 모든 등불이 같은 시각에 꺼진다. 즉 \(D_1 = D_2 = \dots = D_N\)이다. |
Subtask 3 | 50점 | 추가 제한이 없다. |
5
90 2
30 4
60 4
20 7
50 9
5
1 2 4 6 890
60
50
50
50등불들의 \((밝기, 꺼지는\ 시각)\)은 차례로 \((90,2), (30,4), (60,4), (20,7), (50,9)\)이다.
- \(T=1\): \(1{+}\frac{1}{2}\)분 뒤에는 모든 등불이 아직 켜져 있어, 가장 밝은 밝기는 \(90\).
- \(T=2\): \(2{+}\frac{1}{2}\)분 뒤에는 첫 번째 등불 \((90,2)\)이 꺼졌고, 남은 등불 중 가장 밝은 것은 \(60\).
- \(T=4\): \(4{+}\frac{1}{2}\)분 뒤에는 \((20,7), (50,9)\)만 남아 가장 밝은 것은 \(50\).
- \(T=6, 8\): 마찬가지로 가장 밝은 것은 \(50\).
1
1000000000 5
3
0 2 41000000000
1000000000
1000000000등불이 하나뿐이고 \(4{+}\frac{1}{2} < 5\)이므로, 모든 질문에서 그 등불은 여전히 켜져 있다. 따라서 항상 그 밝기 \(1000000000\)을 출력한다.
6
15 1
15 1
80 4
80 4
40 4
20 10
5
0 1 3 4 980
80
80
20
20등불들의 \((밝기, 꺼지는\ 시각)\)은 \((15,1), (15,1), (80,4), (80,4), (40,4), (20,10)\)이다.
- \(T=0\): 모든 등불이 켜져 있어 가장 밝은 것은 \(80\).
- \(T=1\): \(1{+}\frac{1}{2}\)분 뒤에는 꺼지는 시각이 \(1\)인 두 등불이 꺼졌지만, 밝기 \(80\)인 등불이 남아 있어 \(80\).
- \(T=3\): 동일하게 \(80\).
- \(T=4\): 꺼지는 시각이 \(4\)인 등불들이 모두 꺼지고 \((20,10)\)만 남아 \(20\).
- \(T=9\): 마찬가지로 \(20\).
rip 작성
출처 지정되지 않음
평가 및 의견
가장 밝은 등불
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
가장 밝은 등불