// Uloha: KSP-31-3-2 // Autor: Marek Cerny // Email: me@marekcerny.com // -std=c++17 #include #include #include #include #include #include using namespace std; struct node { int val = 0; int max = 0; }; // http://ksp.mff.cuni.cz/kucharky/intervalove-stromy/ struct interval_tree { interval_tree(unsigned size) { aligned_size = _least_greater_or_equal_power(size); // size of tree with internal nodes is 2*aligned size // and for simplicity, we allocate place for unused 'null-leaves' nodes.resize(4*aligned_size); } void update_interval(unsigned from, unsigned to, int value) { _update(from + aligned_size, value); _update(to + aligned_size, -value); } int max_overlap() const { return nodes[1].max; } int _least_greater_or_equal_power(int x) const { int power = 1; while (power < x) power *= 2; return power; } void _update(unsigned inx, int value) { for (; inx > 0; inx /= 2) { nodes[inx].val += value; nodes[inx].max = max( nodes[2*inx].max, nodes[2*inx].val + nodes[2*inx+1].max ); } } unsigned aligned_size; vector nodes; }; unsigned bin_search_index(const vector& array, double value) { // using binary search from standard library return lower_bound(array.begin(), array.end(), value) - array.begin(); } auto unique_sorted_y_coords(const vector>& points, double k) { vector y_coords; for (auto [x, y] : points) { y_coords.push_back(y); y_coords.push_back(y+k); } // sort y-coordinates and then erase duplicities sort(y_coords.begin(), y_coords.end()); y_coords.erase(unique(y_coords.begin(), y_coords.end()), y_coords.end()); return y_coords; } int solve_nlogn(vector> points, double k) { // sort points lexicographically sort(points.begin(), points.end()); vector y_coords = unique_sorted_y_coords(points, k); auto tree = interval_tree(y_coords.size()); int result = 0; queue> lifo; for (auto [a, b] : points) { // add new point lifo.push({a, b}); tree.update_interval( bin_search_index(y_coords, b), bin_search_index(y_coords, b+k), +1 ); // remove x-distant points while (a - lifo.front().first > k) { double y = lifo.front().second; lifo.pop(); tree.update_interval( bin_search_index(y_coords, y), bin_search_index(y_coords, y+k), -1 ); } result = max(result, tree.max_overlap()); } return result; } auto read_input() { int n; cin >> n; double k; cin >> k; auto points = vector>(n); for (auto&& [x, y] : points) cin >> x >> y; return make_tuple(points, k); } int main() { cout << apply(solve_nlogn, read_input()) << endl; return 0; }