루미 알고리즘

#1131실버친구친구

KOI 2026 1차코딩중등부 1번, 고등부 1번출제 정보올림피아드위원회이 문제가 어렵다면 — 배우는 순서 보기

원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)

친구

원제: 친구

문제

KOI 마을에는 일직선 형태의 도로가 있다. 이 도로 위에는 NN개의 집이 있고, 11번부터 NN번까지 번호가 부여된 NN명의 학생이 한 집에 한 명씩 살고 있다. ii (1≤i≤N1 \le i \le N)번 학생이 살고 있는 집의 좌표는 XiX_i이다. 같은 좌표에 여러 개의 집이 존재하지 않는다.

또한, KOI 마을에는 11번부터 NN번까지 번호가 부여된 NN개의 학교들이 있다. ii (1≤i≤N1 \le i \le N)번 학생은 SiS_i번 학교에 다닌다.

ii번 학생과 jj번 학생에 대해 (i≠ji \ne j), 아래의 조건 중 적어도 하나를 만족하면, 두 학생은 서로 친구라고 한다.

  • 두 학생이 서로 같은 학교에 다니고, 두 학생의 집 사이의 거리가 K1K_1 이하이다.
  • 두 학생이 서로 다른 학교에 다니고, 두 학생의 집 사이의 거리가 K2K_2 이하이다.

여기서, 두 집 사이의 거리는 두 집의 좌표 차이의 절댓값으로 정의한다. 즉, ii번 학생과 jj번 학생의 집 사이의 거리는 ∣Xi−Xj∣|X_i - X_j|이다.

각 학생에 대해, 그 학생의 친구가 몇 명인지 계산하는 프로그램을 작성하라. 자기 자신은 자신의 친구가 아님에 유의하라.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 2≤N≤500 0002 \le N \le 500\,000
  • 1≤K1,K2≤1091 \le K_1, K_2 \le 10^9
  • 정수 ii (1≤i≤N1 \le i \le N)에 대하여 1≤Xi≤1091 \le X_i \le 10^9
  • 정수 ii, jj (1≤i<j≤N1 \le i < j \le N)에 대하여 Xi≠XjX_i \ne X_j
  • 정수 ii (1≤i≤N1 \le i \le N)에 대하여 1≤Si≤N1 \le S_i \le N

부분문제

  1. (20점) N≤3 000N \le 3\,000
  2. (14점) K1,K2≤10K_1, K_2 \le 10
  3. (25점) 정수 ii (1≤i≤N1 \le i \le N)에 대하여 Xi≤NX_i \le N이고 Si≤2S_i \le 2
  4. (21점) S1=S2=⋯=SN=1S_1 = S_2 = \cdots = S_N = 1
  5. (10점) 정수 ii (1≤i≤N1 \le i \le N)에 대하여 Si≤2S_i \le 2
  6. (10점) 추가 제약 조건 없음.

입력 형식

첫 줄에 세 정수 NN, K1K_1, K2K_2가 공백으로 구분되어 차례대로 주어진다.

이후 NN개의 줄에 걸쳐 각 학생의 정보가 주어진다. 이 중 ii번째 줄에는 두 정수 XiX_i, SiS_i가 공백으로 구분되어 차례대로 주어진다 (1≤i≤N1 \le i \le N).

출력 형식

첫 줄에 NN개의 정수를 공백으로 구분하여 출력한다. 이 중 ii번째 정수는 ii번 학생의 친구의 수를 의미한다 (1≤i≤N1 \le i \le N).

예제

예제 1

입력
7 3 5
9 2
1 1
14 3
6 2
17 3
4 1
8 1
출력
4 2 2 4 1 3 2

예제 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

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2026년 1차 대회 · 원문 페이지 · 이용 조건 CC BY-NC-SA 4.0 · 원문 그대로 실었으며 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.