{"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__i_ — the broadcasting range of the _i_\\-th station,\n*   _f__i_ — the broadcasting frequency of the _i_\\-th station.\n\nWe 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_|.\n\nLet'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_.\n\nFind the number of bad pairs of radio stations.\n\n## Input\n\nThe 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.\n\nIn 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**.\n\n## Output\n\nOutput the number of bad pairs of radio stations.\n\n[samples]","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)] 为“坏对”，如果 #cf_span[i < j]，基站 #cf_span[i] 和 #cf_span[j] 相互可达，且它们的频率接近，即 #cf_span[|fi - fj| ≤ k]。\n\n求坏对的总数。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ n ≤ 105], #cf_span[0 ≤ k ≤ 10]) —— 无线电基站的数量和相互可达的基站对中频率差的最大值（超过该值则不视为坏对）。\n\n接下来 #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] 个基站的坐标、广播范围和广播频率。*任意两个基站的坐标互不相同*。\n\n## Input\n\n第一行包含两个整数 #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] 个基站的坐标、广播范围和广播频率。*任意两个基站的坐标互不相同*。\n\n## Output\n\n请输出坏对的总数。\n\n[samples]","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 the coordinate,  \n- $ r_i \\in \\mathbb{Z}^+ $ is the broadcasting range,  \n- $ f_i \\in \\mathbb{Z}^+ $ is the frequency.  \nAll $ x_i $ are distinct.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ 0 \\leq k \\leq 10 $  \n3. $ 1 \\leq x_i, r_i \\leq 10^9 $  \n4. $ 1 \\leq f_i \\leq 10^4 $\n\n**Objective**  \nCount the number of unordered pairs $ (i, j) $ with $ i < j $ such that:  \n1. $ \\min(r_i, r_j) \\geq |x_i - x_j| $ (stations reach each other),  \n2. $ |f_i - f_j| \\leq k $ (frequencies are close).  \n\nThat is, compute:  \n$$\n\\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|\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF762E","tags":["binary search","data structures"],"sample_group":[["3 2\n1 3 10\n3 2 5\n4 10 8","1"],["3 3\n1 3 10\n3 2 5\n4 10 8","2"],["5 1\n1 3 2\n2 2 4\n3 2 1\n4 2 1\n5 3 3","2"],["5 1\n1 5 2\n2 5 4\n3 5 1\n4 5 1\n5 5 3","5"]],"created_at":"2026-03-03 11:00:39"}}