2906 - 【入门】相互认识

通过次数

12

提交次数

21

时间限制 : 1 秒
内存限制 : 128 MB

在某国,有 n 户渔民住在海岸线上,整齐的排列成一条直线。每个渔民的房子我们用一个坐标 p_i 来表示,每个渔民的活动半径为 d。也就是说两个距离小于等于 d 的房子,这两户渔民相互认识。

那么在某国,有多少对渔民相互认识?

输入

第一行输入两个整数 n\ (1 \le n \le 10^5)d\ (1 \le d \le 10^4),两数之间以一个空格分隔。

第二行输入 n 个整数 p_i\ (1 \le p_i \le 10^{8}),表示每个渔民房子的坐标(存在坐标相同的 p_i),相邻两数之间以一个空格分隔。

输出

输出一个整数,表示有多少对渔民相互认识。

样例

输入

5 10
10 12 16 37 40

输出

4

提示

直接两两比较每个渔民之间距离,时间复杂度为 \mathcal{O}(n^2),肯定过不了本题。

排序后,对每个渔民 i,统计他右边有多少户渔民和他距离小于等于 d,代码中的 pos 表示右边第一个距离 >d 的位置。

时间复杂度 \mathcal{O}(nlogn)