TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3115
  • Problem
  • P3115[CF762E] 基站 Radio stations
    Limits : Time Limit : 20000 MS   Memory Limit : 262144 KB
    Judgment Tips : 1s,256MB
    Description

    nodgd建设了一些5G基站,但它们之间存在一些干扰。

    所有的基站都建设在了一条直线上,如果将直线视为数轴,则每个基站都有自己的坐标,第 \(i\) 个基站的坐标为 \(x_i\)两个基站不会建设在同一位置

    每个基站设计的功率决定了它的信号覆盖范围,第 \(i\) 个基站的信号覆盖半径是 \(r_i\) ,因此它的信号覆盖范围是坐标区间 \([x_i-r_i, x_i+r_i]\)

    5G网络的无线信号按频率不同分了很多个信道,信道越接近,通讯的干扰就越明显。经过研究表明,如果信道相差超过 \(k\) ,干扰效果就不会影响通讯。

    现在也已经知道了每个基站的信道,第 \(i\) 个基站的信道是 \(f_i\) 。那么问题来了,有多少对基站相互干扰呢?

    两个基站 \(i,j\) 相互干扰,不仅需要相互在对方的信号覆盖范围之内,而且要信道相差不超过 \(k\) 。即:

    \[ |x_i-x_j|\leq \min(r_i,r_j)\\ |f_i-f_j|\leq k \]
    Input Format

    第一行两个整数 \(n,k\) ,表示基站总数和信道相互干扰的条件。

    接下来 \(n\) 行,每行三个数 \(x_i,r_i,f_i\) ,表示一个基站。

    Output Format

    输出一个整数答案。

    Sample Input

    样例输入1
    3 2
    1 3 10
    3 2 5
    4 10 8

    样例输入2
    3 3
    1 3 10
    3 2 5
    4 10 8

    样例输入3
    5 1
    1 3 2
    2 2 4
    3 2 1
    4 2 1
    5 3 3

    样例输入4
    5 1
    1 5 2
    2 5 4
    3 5 1
    4 5 1
    5 5 3

    Sample Output

    样例输出1
    1

    样例输出2
    2

    样例输出3
    2

    样例输出4
    5

    Hint

    $1\leq n\leq 10^5$
    $0\leq k\leq 10$
    $1\leq x_i,r_i\leq 10^9$
    $1\leq f_i\leq 10^4$


    Source  CF762E nodgd搬运并提供数据