← 返回题目列表

Codeforces · 1045/G

G. 人工智能机器人

中文机器翻译题面 查看原题

在上一次任务中,MDCS 已成功将 $$$N$$$ 人工智能机器人运送到火星。在开始探索之前,需要进行系统初始化,因此它们排列成一行。每个机器人都可以用三个数字来描述:位置($$$x_i$$$)、视线半径($$$r_i$$$)和智商($$$q_i$$$)。

由于它们是智能机器人,有些机器人看到对方就会说话。视线半径包含在内,因此机器人可以看到 $$$[x_i - r_i, x_i + r_i]$$$ 范围内的其他所有机器人。但它们不会走路与任何人交谈,而只会与智商相似的机器人交谈。智商相似是指他们的绝对差异不超过$$$K$$$。

帮助我们计算有多少对机器人将相互交谈,以便我们及时更新他们的软件并避免任何潜在的争吵。

输入

第一行包含两个整数,数字 $$$N (1 \leq N \leq 10^5) $$$ 和 $$$K (0 \leq K \leq 20)$$$。

接下来的 $$$N$$$ 行包含三个数字,每个数字 $$$x_i, r_i, q_i (0 \leq x_i,r_i,q_i \leq 10^9)$$$ — 分别是每个机器人的位置、视线半径和智商。

输出

输出仅包含一个数字 — 问题的解决方案。

示例

输入 #1

3 2
3 6 1
7 3 10
10 5 8

输出 #1

1

注意

第一个机器人可以看到第二个机器人,但反之则不然。第一个机器人甚至看不到第三个机器人。第二个和第三个机器人可以看到对方,而且他们的智商相差不超过 2,因此只会发生一次对话。