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.
Examples
input
3 2
1 3 10
3 2 5
4 10 8
output
1
input
3 3
1 3 10
3 2 5
4 10 8
output
2
input
5 1
1 3 2
2 2 4
3 2 1
4 2 1
5 3 3
output
2
input
5 1
1 5 2
2 5 4
3 5 1
4 5 1
5 5 3
output
5
Solution:
#include <bits/stdc++.h> using namespace std; mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count()); class node { public: int id; node* l; node* r; node* p; bool rev; int sz; // declare extra variables: int P; node(int _id) { id = _id; l = r = p = NULL; rev = false; sz = 1; // init extra variables: P = rng(); } void unsafe_reverse() { rev ^= 1; swap(l, r); pull(); } // apply changes: void unsafe_apply() { } void push() { if (rev) { if (l != NULL) { l->unsafe_reverse(); } if (r != NULL) { r->unsafe_reverse(); } rev = 0; } // now push everything else: } void pull() { sz = 1; // now init from self: if (l != NULL) { l->p = this; sz += l->sz; // now pull from l: } if (r != NULL) { r->p = this; sz += r->sz; // now pull from r: } } }; void debug_node(node* v, string pref = "") { #ifdef LOCAL if (v != NULL) { debug_node(v->r, pref + " "); cerr << pref << "-" << " " << v->id << '\n'; debug_node(v->l, pref + " "); } else { cerr << pref << "-" << " " << "NULL" << '\n'; } #endif } namespace treap { pair<node*,int> find(node* v, const function<int(node*)> &go_to) { // go_to returns: 0 -- found; -1 -- go left; 1 -- go right // find returns the last vertex on the descent and its go_to if (v == NULL) { return {NULL, 0}; } int dir; while (true) { v->push(); dir = go_to(v); if (dir == 0) { break; } node* u = (dir == -1 ? v->l : v->r); if (u == NULL) { break; } v = u; } return {v, dir}; } node* get_leftmost(node* v) { return find(v, [&](node*) { return -1; }).first; } node* get_rightmost(node* v) { return find(v, [&](node*) { return 1; }).first; } node* get_kth(node* v, int k) { // 0-indexed pair<node*,int> p = find(v, [&](node* u) { if (u->l != NULL) { if (u->l->sz > k) { return -1; } k -= u->l->sz; } if (k == 0) { return 0; } k--; return 1; }); return (p.second == 0 ? p.first : NULL); } int get_position(node* v) { // 0-indexed int k = (v->l != NULL ? v->l->sz : 0); while (v->p != NULL) { if (v == v->p->r) { k++; if (v->p->l != NULL) { k += v->p->l->sz; } } v = v->p; } return k; } node* get_bst_root(node* v) { while (v->p != NULL) { v = v->p; } return v; } pair<node*,node*> split(node* v, const function<bool(node*)> &is_right) { if (v == NULL) { return {NULL, NULL}; } v->push(); if (is_right(v)) { pair<node*,node*> p = split(v->l, is_right); if (p.first != NULL) { p.first->p = NULL; } v->l = p.second; v->pull(); return {p.first, v}; } else { pair<node*,node*> p = split(v->r, is_right); v->r = p.first; if (p.second != NULL) { p.second->p = NULL; } v->pull(); return {v, p.second}; } } pair<node*,node*> split_leftmost_k(node* v, int k) { return split(v, [&](node* u) { int left_and_me = (u->l != NULL ? u->l->sz : 0) + 1; if (k >= left_and_me) { k -= left_and_me; return false; } return true; }); } node* merge(node* v, node* u) { if (v == NULL) { return u; } if (u == NULL) { return v; } if (v->P > u->P) { // if (rng() % (v->sz + u->sz) < (unsigned int) v->sz) { v->push(); v->r = merge(v->r, u); v->pull(); return v; } else { u->push(); u->l = merge(v, u->l); u->pull(); return u; } } node* add(node* r, node* v, const function<bool(node*)> &go_left) { pair<node*,node*> p = split(r, go_left); return merge(p.first, merge(v, p.second)); } node* remove(node* v) { // returns the new root v->push(); node* x = v->l; node* y = v->r; node* p = v->p; v->l = v->r = v->p = NULL; v->push(); v->pull(); // now v might be reusable... node* z = merge(x, y); if (p == NULL) { if (z != NULL) { z->p = NULL; } return z; } if (p->l == v) { p->l = z; } if (p->r == v) { p->r = z; } while (true) { p->push(); p->pull(); if (p->p == NULL) { break; } p = p->p; } return p; } node* next(node* v) { if (v->r == NULL) { while (v->p != NULL && v->p->r == v) { v = v->p; } return v->p; } v->push(); v = v->r; while (v->l != NULL) { v->push(); v = v->l; } return v; } node* prev(node* v) { if (v->l == NULL) { while (v->p != NULL && v->p->l == v) { v = v->p; } return v->p; } v->push(); v = v->l; while (v->r != NULL) { v->push(); v = v->r; } return v; } int get_size(node* v) { return (v != NULL ? v->sz : 0); } template<typename... T> void apply(node* v, T... args) { v->unsafe_apply(args...); } void reverse(node* v) { v->unsafe_reverse(); } } using namespace treap; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; vector<int> x(n), r(n), f(n); for (int i = 0; i < n; i++) { cin >> x[i] >> r[i] >> f[i]; } vector<int> order(n); iota(order.begin(), order.end(), 0); sort(order.begin(), order.end(), [&](int i, int j) { return r[i] > r[j]; }); const int MAX = 10010; vector<node*> nodes(MAX, NULL); long long ans = 0; for (int i : order) { for (int j = max(0, f[i] - k); j <= min(MAX - 1, f[i] + k); j++) { pair<node*,node*> p = split(nodes[j], [&](node* v) { return x[i] + r[i] < v->id; }); pair<node*,node*> q = split(p.first, [&](node* v) { return x[i] - r[i] <= v->id; }); ans += get_size(q.second); nodes[j] = merge(q.first, merge(q.second, p.second)); } nodes[f[i]] = add(nodes[f[i]], new node(x[i]), [&](node* v) { return x[i] < v->id; }); } cout << ans << '\n'; return 0; }