E. Radio stations

Codeforces

IDCF762E

Time2000ms

Memory256MB

Difficulty—

binary searchdata structures

English · Original

Chinese · Translation

Formal · Original

In the lattice points of the coordinate line there are _n_ radio stations, the _i_\-th of which is described by three integers: * _x__i_ — the coordinate of the _i_\-th station on the line, * _r__i_ — the broadcasting range of the _i_\-th station, * _f__i_ — the broadcasting frequency of the _i_\-th station. We will say that two radio stations with numbers _i_ and _j_ reach each other, if the broadcasting range of each of them is more or equal to the distance between them. In other words _min_(_r__i_, _r__j_) ≥ |_x__i_ - _x__j_|. Let's call a pair of radio stations (_i_, _j_) bad if _i_ < _j_, stations _i_ and _j_ reach each other and they are close in frequency, that is, |_f__i_ - _f__j_| ≤ _k_. Find the number of bad pairs of radio stations. ## Input The first line contains two integers _n_ and _k_ (1 ≤ _n_ ≤ 105, 0 ≤ _k_ ≤ 10) — the number of radio stations and the maximum difference in the frequencies for the pair of stations that reach each other to be considered bad. In the next _n_ lines follow the descriptions of radio stations. Each line contains three integers _x__i_, _r__i_ and _f__i_ (1 ≤ _x__i_, _r__i_ ≤ 109, 1 ≤ _f__i_ ≤ 104) — the coordinate of the _i_\-th radio station, it's broadcasting range and it's broadcasting frequency. **No two radio stations will share a coordinate**. ## Output Output the number of bad pairs of radio stations. [samples]

在坐标轴的整数点上有 #cf_span[n] 个无线电基站，第 #cf_span[i] 个基站由三个整数描述：我们称两个编号为 #cf_span[i] 和 #cf_span[j] 的无线电基站相互可达，当且仅当它们的广播范围均不小于它们之间的距离。换句话说，#cf_span[min(ri, rj) ≥ |xi - xj|]。我们称一对无线电基站 #cf_span[(i, j)] 为“坏对”，如果 #cf_span[i < j]，基站 #cf_span[i] 和 #cf_span[j] 相互可达，且它们的频率接近，即 #cf_span[|fi - fj| ≤ k]。求坏对的总数。第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ n ≤ 105], #cf_span[0 ≤ k ≤ 10]) —— 无线电基站的数量和相互可达的基站对中频率差的最大值（超过该值则不视为坏对）。接下来 #cf_span[n] 行，每行描述一个基站，包含三个整数 #cf_span[xi], #cf_span[ri] 和 #cf_span[fi] (#cf_span[1 ≤ xi, ri ≤ 109], #cf_span[1 ≤ fi ≤ 104]) —— 第 #cf_span[i] 个基站的坐标、广播范围和广播频率。*任意两个基站的坐标互不相同*。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ n ≤ 105], #cf_span[0 ≤ k ≤ 10]) —— 无线电基站的数量和相互可达的基站对中频率差的最大值（超过该值则不视为坏对）。接下来 #cf_span[n] 行，每行描述一个基站，包含三个整数 #cf_span[xi], #cf_span[ri] 和 #cf_span[fi] (#cf_span[1 ≤ xi, ri ≤ 109], #cf_span[1 ≤ fi ≤ 104]) —— 第 #cf_span[i] 个基站的坐标、广播范围和广播频率。*任意两个基站的坐标互不相同*。 ## Output 请输出坏对的总数。 [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $, $ k \in \mathbb{Z}_{\geq 0} $. Let $ S = \{ (x_i, r_i, f_i) \mid i \in \{1, \dots, n\} \} $ be a set of radio stations, where: - $ x_i \in \mathbb{Z} $ is the coordinate, - $ r_i \in \mathbb{Z}^+ $ is the broadcasting range, - $ f_i \in \mathbb{Z}^+ $ is the frequency. All $ x_i $ are distinct. **Constraints** 1. $ 1 \leq n \leq 10^5 $ 2. $ 0 \leq k \leq 10 $ 3. $ 1 \leq x_i, r_i \leq 10^9 $ 4. $ 1 \leq f_i \leq 10^4 $ **Objective** Count the number of unordered pairs $ (i, j) $ with $ i < j $ such that: 1. $ \min(r_i, r_j) \geq |x_i - x_j| $ (stations reach each other), 2. $ |f_i - f_j| \leq k $ (frequencies are close). That is, compute: $$ \left| \left\{ (i, j) \in \{1, \dots, n\}^2 \mid i < j,\ \min(r_i, r_j) \geq |x_i - x_j|,\ |f_i - f_j| \leq k \right\} \right| $$

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

Input #4

Output #4

API Response (JSON)

{
  "problem": {
    "name": "E. Radio stations",
    "description": {
      "content": "In the lattice points of the coordinate line there are _n_ radio stations, the _i_\\-th of which is described by three integers: *   _x__i_ — the coordinate of the _i_\\-th station on the line, *   _r_",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF762E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "In the lattice points of the coordinate line there are _n_ radio stations, the _i_\\-th of which is described by three integers:\n\n*   _x__i_ — the coordinate of the _i_\\-th station on the line,\n*   _r_...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在坐标轴的整数点上有 #cf_span[n] 个无线电基站，第 #cf_span[i] 个基站由三个整数描述：\n\n我们称两个编号为 #cf_span[i] 和 #cf_span[j] 的无线电基站相互可达，当且仅当它们的广播范围均不小于它们之间的距离。换句话说，#cf_span[min(ri, rj) ≥ |xi - xj|]。\n\n我们称一对无线电基站 #cf_span[(i, j)] 为“坏对”...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, $ k \\in \\mathbb{Z}_{\\geq 0} $.  \nLet $ S = \\{ (x_i, r_i, f_i) \\mid i \\in \\{1, \\dots, n\\} \\} $ be a set of radio stations, where:  \n- $ x_i \\in \\mathbb{Z} ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments