結果

問題 No.3456 Common Difference is D
コンテスト
ユーザー zame takoyaki
提出日時 2026-04-01 14:22:18
言語 C
(gcc 15.2.0)
コンパイル:
gcc-15 -O2 -DONLINE_JUDGE -o a.out _filename_ -lm
実行:
./a.out
結果
AC  
実行時間 61 ms / 2,000 ms
コード長 1,173 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,292 ms
コンパイル使用メモリ 39,240 KB
実行使用メモリ 47,084 KB
最終ジャッジ日時 2026-04-01 14:22:21
合計ジャッジ時間 2,889 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <stdio.h>
#include <stdlib.h> 
#define MAX 100000

int cmp_ll(const void *a, const void *b){
	int  x = *(int *)a; 
	int  y = *(int *)b; 
	
	if(x < y) return -1; 
	if(x > y) return 1; 
	return 0; 
} 

int find( int N, int target, int *uniq){
	int left= 0;
	int right = N-1;
	
	while(left <= right){
		int mid = (left + right)/2;
		
		if (uniq[mid] < target) left =mid+1;
		else if(uniq[mid]==target) return mid ;
		else right = mid-1;
	}
	return -1; 
}



int main(void){
	int N,D; 
	int A[MAX]={0}, sortA[MAX]={0}, uniq[MAX]={0}, freqL[MAX]={0}, freqR[MAX]={0}; 
	int M=0;
	long long ans = 0;
	int MAX_number=0;
	scanf("%d", &N); scanf("%d", &D); 
	
	for(int l = 0; l < N ; l++){
		scanf("%d", &A[l]); 
		sortA[l] = A[l]; 
	} 
	
	qsort(sortA, N, sizeof(int), cmp_ll); 
	
	for(int l= 0; l < N ; l++){ 
		if(l == 0 || sortA[l] != sortA[l-1]){
			uniq[M]=sortA[l]; 
			M++; 
		}
		freqR[M-1]++;
	}
	
	for(int l = 0; l < N ;l++){
		int x=A[l];
		int idR = find(M, x, uniq);
		freqR[idR]--;
		int i = find(M, x-D, uniq);
		int k = find(M, x+D, uniq);
		
		if(i != -1 && k != -1){
			ans += freqL[i]* freqR[k];
		}
	freqL[idR]++;
	}
	printf("%lld", ans);	
	return 0;
}
0