친구
골드 IV의견: 0
KOI 마을에는 일직선 형태의 도로가 있다. 이 도로 위에는 \(N\)개의 집이 있고, \(1\)번부터 \(N\)번까지 번호가 부여된 \(N\)명의 학생이 한 집에 한 명씩 살고 있다. \(i\) (\(1 \le i \le N\))번 학생이 살고 있는 집의 좌표는 \(X_i\)이다. 같은 좌표에 여러 개의 집이 존재하지 않는다.
또한, KOI 마을에는 \(1\)번부터 \(N\)번까지 번호가 부여된 \(N\)개의 학교들이 있다. \(i\) (\(1 \le i \le N\))번 학생은 \(S_i\)번 학교에 다닌다.
\(i\)번 학생과 \(j\)번 학생에 대해 (\(i \ne j\)), 아래의 조건 중 적어도 하나를 만족하면, 두 학생은 서로 친구라고 한다.
- 두 학생이 서로 같은 학교에 다니고, 두 학생의 집 사이의 거리가 \(K_1\) 이하이다.
- 두 학생이 서로 다른 학교에 다니고, 두 학생의 집 사이의 거리가 \(K_2\) 이하이다.
여기서, 두 집 사이의 거리는 두 집의 좌표 차이의 절댓값으로 정의한다. 즉, \(i\)번 학생과 \(j\)번 학생의 집 사이의 거리는 \(|X_i - X_j|\)이다.
각 학생에 대해, 그 학생의 친구가 몇 명인지 계산하는 프로그램을 작성하라. 자기 자신은 자신의 친구가 아님에 유의하라.
주어지는 모든 수는 정수이다.
- \(2 \le N \le 500\,000\)
- \(1 \le K_1, K_2 \le 10^9\)
- 모든 \(i\) (\(1 \le i \le N\))에 대하여 \(1 \le X_i \le 10^9\)
- 모든 \(i, j\) (\(1 \le i < j \le N\))에 대하여 \(X_i \ne X_j\)
- 모든 \(i\) (\(1 \le i \le N\))에 대하여 \(1 \le S_i \le N\)
첫 줄에 세 정수 \(N\), \(K_1\), \(K_2\)가 공백으로 구분되어 차례대로 주어진다.
이후 \(N\)개의 줄에 걸쳐 각 학생의 정보가 주어진다. 이 중 \(i\)번째 줄에는 두 정수 \(X_i\), \(S_i\)가 공백으로 구분되어 차례대로 주어진다 (\(1 \le i \le N\)).
첫 줄에 \(N\)개의 정수를 공백으로 구분하여 출력한다. 이 중 \(i\)번째 정수는 \(i\)번 학생의 친구의 수를 의미한다 (\(1 \le i \le N\)).
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 20점 | \(N \le 3\,000\) |
2 | 14점 | \(K_1, K_2 \le 10\) |
3 | 25점 | 모든 \(i\) (\(1 \le i \le N\))에 대하여 \(X_i \le N\)이고 \(S_i \le 2\)이다. |
4 | 21점 | \(S_1 = S_2 = \cdots = S_N = 1\) |
5 | 10점 | 모든 \(i\) (\(1 \le i \le N\))에 대하여 \(S_i \le 2\)이다. |
6 | 10점 | 추가 제약 조건 없음. |
7 3 5
9 2
1 1
14 3
6 2
17 3
4 1
8 1
4 2 2 4 1 3 2
12 8 5
31 1
10 1
49 3
23 2
62 3
18 1
40 2
14 2
55 2
27 3
45 1
36 3
2 2 1 2 0 3 2 2 0 2 2 2
riseoj 작성
출처 올림피아드 > 한국정보올림피아드 > KOI 2026 > 1차 대회 > 중등부 1번 / 고등부 1번
평가 및 의견
친구
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
친구