5212 : A13 - 가까운 쌍 (Close Pairs)
•시간제한: 1.000 S
•메모리제한: 1024 MB
•제출: 1
•통과: 1
•만든사람: suakii
문제 설명
$N$ 개의 정수가 오름차순으로 $A_1, A_2, \dots, A_N$ 과 같이 주어집니다.
서로 다른 두 정수의 쌍을 고르는 방법은 총 $N(N-1)/2$ 가지가 있는데, 그 중에서 두 수의 차가 $K$ 이하인 쌍은 몇 가지인지 구하는 프로그램을 작성하세요.
[제약 조건]
• $1 \le N \le 100\,000$
• $1 \le K \le 10^9$
• $1 \le A_1 < A_2 < \cdots < A_N \le 10^9$
• 입력되는 모든 값은 정수입니다.
서로 다른 두 정수의 쌍을 고르는 방법은 총 $N(N-1)/2$ 가지가 있는데, 그 중에서 두 수의 차가 $K$ 이하인 쌍은 몇 가지인지 구하는 프로그램을 작성하세요.
[제약 조건]
• $1 \le N \le 100\,000$
• $1 \le K \le 10^9$
• $1 \le A_1 < A_2 < \cdots < A_N \le 10^9$
• 입력되는 모든 값은 정수입니다.
입력 설명
$N$ $K$
$A_1$ $A_2$ $\dots$ $A_N$
$A_1$ $A_2$ $\dots$ $A_N$
출력 설명
차가 $K$ 이하인 정수 쌍의 개수를 한 줄로 출력하세요.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
7 10
11 12 16 22 27 28 31
출력 예시
COPY
복사되었습니다!
복사되었습니다!
11