R00987
음정 차이
실버 II레이팅
의견: 0
설명
작곡가 하린이는 \(N\)개의 음을 적어 두었다. 각 음의 높이는 정수이다.
하린이는 높이 차이가 정확히 \(K\)인 두 음의 쌍이 화음으로 쓰기 좋다고 생각한다. 서로 다른 두 음표 \(i < j\) 중에서 \(|a_i - a_j| = K\)를 만족하는 쌍의 개수를 구하여라. \(K = 0\)이면 높이가 같은 두 음표의 쌍을 세면 된다.
제약
- \(2 \le N \le 200\,000\)
- \(0 \le K \le 2 \times 10^9\)
- \(-10^9 \le a_i \le 10^9\)
입력 형식
첫째 줄에 음의 수 \(N\)과 차이 \(K\)가 공백으로 구분되어 주어진다.
둘째 줄에 음의 높이 \(a_1, a_2, \dots, a_N\)이 공백으로 구분되어 주어진다.
출력 형식
조건을 만족하는 쌍의 개수를 출력한다. 답이 \(32\)비트 정수 범위를 넘을 수 있음에 주의하여라.
예제 1
입력
4 2
1 3 3 5
출력
4
설명
음 \(1\)과 두 개의 \(3\), 그리고 두 개의 \(3\)과 음 \(5\)가 각각 차이 \(2\)를 이루므로 모두 \(4\)쌍이다.
예제 2
입력
3 0
7 7 7
출력
3
설명
높이가 같은 세 음에서 두 개를 고르는 방법은 \(3\)가지이다.
힌트
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
힌트 1
로그인하고 잠금 해제 · 10 🪙
힌트 2
로그인하고 잠금 해제 · 20 🪙
문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
음정 차이
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
음정 차이
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기