25440번 - 송신탑 서브태스크다국어언어 제한함수 구현
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 55 | 17 | 16 | 31.373% |
문제
자카르타에는 $N$개의 송신탑이 있다. 송신탑들은 일직선 상에 위치하며 왼쪽에서 오른쪽으로 $0$부터 $N - 1$까지 번호가 붙어 있다. $0 \le i \le N - 1$인 각 $i$에 대해, 송신탑 $i$의 높이는 $H[i]$ 미터이다. 송신탑들의 높이는 모두 다르다.
어떤 양의 간섭 수치 $\delta$에 대해, 한 쌍의 송신탑 $i$와 $j$ ($0 \le i \lt j \le N - 1$)가 서로 통신할 수 있다는 것은 다음을 모두 만족하는 중개 송신탑 $k$가 존재한다는 것을 의미한다.
- 송신탑 $i$는 송신탑 $k$의 왼쪽에 위치하고 송신탑 $j$는 송신탑 $k$의 오른쪽에 위치한다. 즉, $i \lt k \lt j$이다.
- 송신탑 $i$와 $j$의 높이는 최대 $H[k] - \delta$ 미터이다.
팍 뎅클렉은 자신의 새로운 송신 네트워크를 위해 몇 개의 송신탑을 빌리려고 한다. 당신은 다음과 같은 팍 뎅클렉의 질문 $Q$개에 대해 답변해야 한다: 파라미터 $L, R$과 $D$ ($0 \le L \le R \le N - 1$이고 $D > 0$)가 주어지면, 팍 뎅클렉이 빌릴 수 있는 송신탑의 최대 개수는 몇 개인가? 단, 다음을 가정한다:
- 팍 뎅클렉은 번호 $L$과 $R$ 사이($L$과 $R$ 포함)의 송신탑만 빌릴 수 있고,
- 간섭 수치 $\delta$는 $D$이고,
- 팍 뎅클렉이 빌리는 송신탑들은 어떤 쌍을 선택하던지 서로 통신할 수 있어야 한다.
참고로 빌린 두 송신탑이 중개 송신탑 $k$를 이용하여 통신할 수 있을 때, 송신탑 $k$는 빌렸어도 되고 빌리지 않았어도 된다.
구현
다음 함수를 구현해야 한다:
void init(int N, int[] H)
- $N$: 송신탑의 개수.
- $H$: 송신탑의 높이를 나타내는 길이 $N$인 배열.
- 이 함수는 최초에 한번만 호출된다. 이후에 아래에 설명된
max_towers호출이 이어진다.
int max_towers(int L, int R, int D)
- $L$, $R$: 송신탑 범위의 경계.
- $D$: 간섭 수치 $\delta$.
- 이 함수는 팍 뎅클렉이 빌릴 수 있는 송신탑의 범위가 $L$과 $R$ 사이($L$과 $R$ 포함)로 한정되고 간섭 수치 $\delta$가 $D$일 때 그가 빌릴 수 있는 송신탑의 최대 개수를 리턴해야 한다.
- 이 함수는 정확히 $Q$번 호출된다.
예제
다음 호출을 생각해보자:
init(7, [10, 20, 60, 40, 50, 30, 70])
max_towers(1, 5, 10)
팍 뎅클렉은 송신탑 $1$, $3$, 그리고 $5$를 빌릴 수 있다. 아래 그림에서 색칠된 사다리꼴이 빌린 송신탑을 나타낸다.
$40 \le 50 - 10$이고 $30 \le 50 - 10$이므로 송신탑 $3$과 $5$는 송신탑 $4$를 중개 송신탑으로 이용해서 서로 통신할 수 있다. 송신탑 $1$과 $3$은 중개 송신탑 $2$를 이용하여 서로 통신할 수 있다. 송신탑 $1$과 $5$는 중개 송신탑 $3$을 이용하여 서로 통신할 수 있다. $3$개보다 더 많은 송신탑을 빌릴 수 있는 방법이 없으므로, 함수는 $3$을 리턴해야 한다.
max_towers(2, 2, 100)
범위에 포함되는 송신탑이 $1$개 밖에 없으므로, 팍 뎅클렉은 오직 $1$개의 송신탑만 빌릴 수 있다. 따라서 함수는 $1$을 리턴해야 한다.
max_towers(0, 6, 17)
팍 뎅클렉은 송신탑 $1$과 $3$을 빌릴 수 있다. $20 \le 60 - 17$이고 $40 \le 60 - 17$이므로 송신탑 $1$과 $3$은 중개 송신탑 $2$를 이용하여 서로 통신할 수 있다. $2$개보다 더 많은 송신탑을 빌릴 수 있는 방법이 없으므로, 함수는 $2$를 리턴해야 한다.
제한
- $1 \le N \le 100\,000$
- $1 \le Q \le 100\,000$
- $1 \le H[i] \le 10^9$ (모든 $0 \le i \le N - 1$)
- $H[i] \ne H[j]$ (모든 $0 \le i \lt j \le N - 1$)
- $0 \le L \le R \le N - 1$
- $1 \le D \le 10^9$
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 4 | 다음을 모두 만족하는 송신탑 $k$ ($0 \le k \le N - 1$)가 존재한다.
|
| 2 | 11 | $Q = 1$, $N \le 2000$ |
| 3 | 12 | $Q = 1$ |
| 4 | 14 | $D = 1$ |
| 5 | 17 | $L = 0$, $R = N - 1$ |
| 6 | 19 | 모든 |
| 7 | 23 | 추가적인 제한이 없다. |
샘플 그레이더
샘플 그레이더의 입력 양식은 다음과 같다:
- line $1$: $N \, Q$
- line $2$: $H[0] \, H[1] \, \ldots \, H[N - 1]$
- line $3 + j$ ($0 \le j \le Q - 1$): $L \, R \, D$ ($j$번째 질문을 위한 $L$, $R$, $D$임)
샘플 그레이더는 다음 형식으로 답을 출력한다:
- line $1 + j$ ($0 \le j \le Q - 1$): $j$번째
max_towers호출의 리턴값
첨부
출처
Olympiad > International Olympiad in Informatics > IOI 2022 > Day 1 3번
- 문제를 만든 사람: Kevin Luiz Ponte Pucci
제출할 수 있는 언어
C++17, C++20, C++17 (Clang), C++20 (Clang)
채점 및 기타 정보
- 예제는 채점하지 않는다.
- 이 문제의 채점 우선 순위는 2이다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호