You are given n integers a₁ … aₙ and an integer k.
Print how many pairs of positions i < j satisfy |aᵢ − aⱼ| ≤ k.
Equal values at different positions count as different numbers.
The same two positions in swapped order (i, j and j, i) are one pair.
If n = 1 the answer is 0.
The first line gives n and k, and the second line gives a₁ … aₙ, separated by spaces.
Input
1 ≤ n ≤ 10,000, −2×10⁹ ≤ aᵢ ≤ 2×10⁹, 0 ≤ k ≤ 10⁹
Output
The number of pairs
Example 1 · stdin
5 3
1 9 4 7 3
stdout
5
Example 2 · stdin
2 1000000000
-2000000000 2000000000
stdout
0
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Trying every pair is n²/2 = 50 million checks, so Craykon passes its execution-step limit (about 50 million) and Python is slow. After sorting, the numbers within k of a[j] form one block right before it, a[i..j−1], and as j moves right, i only moves right too (two pointers). So it takes a sort (n log n) plus a 2n scan. Sorting differs by language. Python sorted(), Java Arrays.sort(), C# Array.Sort() and C++ std::sort put numbers in order of size. Craykon a.Sort() without a comparison function also sorts numbers from small to large. But JavaScript/TypeScript sort()without a comparison function converts to strings and sorts in dictionary order, so 10 comes before 9 and -1 before -2 — pass a function as in a.sort((x, y) => x - y). C's qsort also takes the comparison as a function pointer, and the common return x - y; overflows int at 2×10⁹ − (−2×10⁹) and flips the order — compare only the sizes with (x > y) - (x < y). The same overflow hides in the two-pointer a[j] - a[i]: the difference reaches 4×10⁹, so Java, C#, C and C++ must subtract in long/long long, or example 2 prints 1. And since the rule is 'at most k', move i only while the difference is > k — moving it on >= k loses pairs of equal values when k = 0.
Pythonmain.py · 12 lines
n, k = map(int, input().split())a = sorted(map(int, input().split()))# 정렬하면 a[j]와 차이가 k 이하인 것은 a[j] 바로 앞의 한 구간이다.# j가 오른쪽으로 갈수록 구간의 왼쪽 끝 i도 오른쪽으로만 간다(두 포인터).count = 0i = 0for j in range(n): while a[j] - a[i] > k: i += 1 count += j - i # a[i..j-1]이 모두 짝이 된다print(count)
JavaScriptmain.js · 12 lines
const [n, k, ...a] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);// sort()에 비교 함수를 넘기지 않으면 문자열로 바꿔 사전 순으로 늘어놓는다(10이 9보다 앞)a.sort((x, y) => x - y);// a[j]와 차이가 k 이하인 것은 a[j] 바로 앞의 한 구간이다. 왼쪽 끝 i는 오른쪽으로만 간다.let count = 0;let i = 0;for (let j = 0; j < n; j++) { while (a[j] - a[i] > k) i++; count += j - i;}console.log(count);
TypeScriptmain.ts · 14 lines
import { readFileSync } from "node:fs";const [n, k, ...a]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);// sort()에 비교 함수를 넘기지 않으면 문자열로 바꿔 사전 순으로 늘어놓는다(10이 9보다 앞)a.sort((x: number, y: number): number => x - y);// a[j]와 차이가 k 이하인 것은 a[j] 바로 앞의 한 구간이다. 왼쪽 끝 i는 오른쪽으로만 간다.let count = 0;let i = 0;for (let j = 0; j < n; j++) { while (a[j] - a[i] > k) i++; count += j - i;}console.log(count);
JavaMain.java · 27 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken()); int[] a = new int[n]; st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken()); Arrays.sort(a); // a[j]와 차이가 k 이하인 것은 a[j] 바로 앞의 한 구간이다. 왼쪽 끝 i는 오른쪽으로만 간다. long count = 0; int i = 0; for (int j = 0; j < n; j++) { while ((long) a[j] - a[i] > k) i++; // 차이는 4×10⁹까지라 long으로 뺀다 count += j - i; } System.out.println(count); }}
C#Main.cs · 24 lines
using System;using System.Linq;class Program{ static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(first[0]); long k = long.Parse(first[1]); long[] a = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(long.Parse).ToArray(); Array.Sort(a); // a[j]와 차이가 k 이하인 것은 a[j] 바로 앞의 한 구간이다. 왼쪽 끝 i는 오른쪽으로만 간다. long count = 0; int i = 0; for (int j = 0; j < n; j++) { while (a[j] - a[i] > k) i++; // long이라 4×10⁹ 차이도 넘치지 않는다 count += j - i; } Console.WriteLine(count); }}
C++main.cpp · 21 lines
#include <algorithm>#include <iostream>#include <vector>int main() { int n; long long k; std::cin >> n >> k; std::vector<long long> a(n); for (long long& x : a) std::cin >> x; std::sort(a.begin(), a.end()); // a[j]와 차이가 k 이하인 것은 a[j] 바로 앞의 한 구간이다. 왼쪽 끝 i는 오른쪽으로만 간다. long long count = 0; int i = 0; for (int j = 0; j < n; j++) { while (a[j] - a[i] > k) i++; count += j - i; } std::cout << count << "\n";}
Cmain.c · 27 lines
#include <stdio.h>#include <stdlib.h>static int a[10000];/* qsort에 넘기는 비교 함수. x - y로 돌려주면 int를 넘칠 수 있어서 크기만 비교한다. */static int ascending(const void* p, const void* q) { int x = *(const int*)p, y = *(const int*)q; return (x > y) - (x < y);}int main(void) { int n, k; scanf("%d %d", &n, &k); for (int i = 0; i < n; i++) scanf("%d", &a[i]); qsort(a, n, sizeof a[0], ascending); /* a[j]와 차이가 k 이하인 것은 a[j] 바로 앞의 한 구간이다. 왼쪽 끝 i는 오른쪽으로만 간다. */ long long count = 0; int i = 0; for (int j = 0; j < n; j++) { while ((long long)a[j] - a[i] > k) i++; /* 차이는 4×10⁹까지 */ count += j - i; } printf("%lld\n", count); return 0;}
Craykonmain.cray · 19 lines
첫줄 = Console.ReadNumbers();n = 첫줄[0];k = 첫줄[1];a = Console.ReadNumbers();// 기준 함수를 주지 않으면 수는 작은 것부터 늘어놓는다a.Sort();// a[j]와 차이가 k 이하인 것은 a[j] 바로 앞의 한 구간이다. 왼쪽 끝 i는 오른쪽으로만 간다.count = 0;i = 0;for (j = 0; j < n; j++){ while (a[j] - a[i] > k) { i += 1; } count += j - i;}Console.WriteLine(count);