Matcom Online Grader
<p style='text-align: justify;'>In the last mission, MDCS has sucessfully shipped $N$ AI robots to Mars. Before they started exploring, they were arranged in a line. Every robot can be described with **three** numbers: position ($x_i$), radius of vision ($r_i$) and IQ ($q_i$). Since they are intelligent robots they are very talkative. Two robots can talk if they can see each other. However, they don't walk to talk with any robot, but only with robots who have similar IQ. By similar IQ we mean that absolute difference in their IQs **isn't bigger than $K$**.Help us and calculate how many pairs of robots are going to talk with each other, so we can timely update their software and avoid possible fights.</p>*Note: Radius of vision is inclusive.*
In the last mission, MDCS has sucessfully shipped $N$ AI robots to Mars. Before they started exploring, they were arranged in a line. Every robot can be described with three numbers: position ($x_i$), radius of vision ($r_i$) and IQ ($q_i$). Since they are intelligent robots they are very talkative. Two robots can talk if they can see each other. However, they don't walk to talk with any robot, but only with robots who have similar IQ. By similar IQ we mean that absolute difference in their IQs isn't bigger than $K$.
Help us and calculate how many pairs of robots are going to talk with each other, so we can timely update their software and avoid possible fights.
Note: Radius of vision is inclusive.
Input
<p style='text-align: justify;'>The first line contains two integers, number $N$ and $K$. Next $N$ lines contain three numbers each – $x_i$, $r_i$ and $q_i$ respectively.</p>Constraints:* 1 ≤ $N$ ≤ $10^5$* 0 ≤ $x_i$, $r_i$, $q_i$ ≤ $10^9$* 0 ≤ $K$ ≤ 20
The first line contains two integers, number $N$ and $K$. Next $N$ lines contain three numbers each – $x_i$, $r_i$ and $q_i$ respectively.
Constraints:
- 1 ≤ $N$ ≤ $10^5$
- 0 ≤ $x_i$, $r_i$, $q_i$ ≤ $10^9$
- 0 ≤ $K$ ≤ 20
Output
Output contains only one number – solution of the problem.Output contains only one number – solution of the problem.
Sample test(s)
Hints
<p style='text-align: justify;'>Explanation:The first robot can see the second, but not vice versa. The first robot can't even see the third. The second and the third robot can see each other and their IQs don't differ more than 2 so only one pair of robots will have a talk.</p>
Explanation:
The first robot can see the second, but not vice versa. The first robot can't even see the third. The second and the third robot can see each other and their IQs don't differ more than 2 so only one pair of robots will have a talk.