점프
다이아몬드 V의견: 0
이차원 좌표 평면에 \(1\)번부터 \(N\)번까지 번호가 부여된 \(N\)개의 발판이 있다. 각 발판은 좌표 평면 위의 한 점으로 표현할 수 있고, \(i\) (\(1 \le i \le N\))번 발판의 위치 좌표는 \((X_i, i)\)이다.
두 정수 \(i\), \(j\) (\(1 \le i, j \le N\))에 대해, 아래의 두 조건을 모두 만족할 때에만 \(i\)번 발판에서 \(j\)번 발판으로 이동할 수 있다.
- \(i < j\)
- \(|X_i - X_j| \le D\)
여기서, \(D\)는 주어지는 상수이며, 양의 정수 값을 가진다.
각 발판에 대하여, 그 발판에서 시작해서 다른 발판으로 이동하는 것을 \(0\)번 이상 반복하여 도달할 수 있는 서로 다른 발판의 개수를 세는 프로그램을 작성하라. 이 개수에는 그 발판 자기 자신도 포함되어야 함에 유의하라.
- 주어지는 모든 수는 정수이다.
- \(1 \le N \le 300\,000\)
- \(1 \le D \le 10^9\)
- 모든 \(i\) (\(1 \le i \le N\))에 대하여 \(1 \le X_i \le 10^9\)
첫 줄에 두 정수 \(N\), \(D\)가 공백으로 구분되어 차례대로 주어진다.
그다음 줄에 \(N\)개의 정수 \(X_1, X_2, \cdots, X_N\)이 공백으로 구분되어 차례대로 주어진다.
첫 줄에 \(N\)개의 정수를 공백으로 구분하여 출력한다. 이 중 \(i\)번째 정수는 \(i\)번 발판에서 시작해서 다른 발판으로 이동하는 것을 \(0\)번 이상 반복하여 도달할 수 있는 서로 다른 발판의 개수를 의미한다 (\(1 \le i \le N\)).
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 12점 | \(N \le 300\) |
2 | 32점 | \(N \le 7\,500\) |
3 | 9점 | \(X_1 \le X_2 \le \cdots \le X_N\) |
4 | 23점 | 모든 \(i\) (\(1 \le i \le N\))에 대하여 \(X_i \le 30\)이다. |
5 | 33점 | \(D = 1\) |
6 | 41점 | 추가적인 제약 조건 없음. |
6 2
3 5 4 6 1 3
6 4 3 1 2 1
각 발판에 대하여 해당 발판에서 시작해서 도달할 수 있는 발판은 다음과 같다.
- \(1\)번 발판: 자기 자신을 포함하여 모든 발판(\(1, 2, 3, 4, 5, 6\)번)으로 도달 가능하다.
- \(2\)번 발판: \(2, 3, 4, 6\)번 발판으로 도달 가능하다.
- \(3\)번 발판: \(3, 4, 6\)번 발판으로 도달 가능하다.
- \(4\)번 발판: 자기 자신(\(4\)번)을 제외하고 도달할 수 있는 발판이 없다.
- \(5\)번 발판: \(5, 6\)번 발판으로 도달 가능하다.
- \(6\)번 발판: 자기 자신(\(6\)번)을 제외하고 도달할 수 있는 발판이 없다.
6 3
1 4 8 9 10 15
2 1 3 2 1 1
3 2
1 4 7
1 1 1
riseoj 작성
출처 올림피아드 > 한국정보올림피아드 > KOI 2026 > 1차 대회 > 고등부 3번
평가 및 의견
점프
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
점프