Problem: Example

Input

5 3
1 5
3 4
5 3
7 2
9 1


Output

5

Solution (in CPP):

Solution:
//
// Problem: Rough Minimum
// Solution by: MORI Shingo
// O(nlogn)
//
// implement 49min
// debug 48min
// 
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);
const int INF = 2e+9 + 3;

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))


struct Node {
  int index;
  int first;
  int second;
  Node() {;}
  Node(int index, int first, int second) : index(index), first(first), second(second) {;}
};

inline Node Merge(Node left, Node right) {
  if (left.second < right.second) { return left; }
  if (left.second > right.second) { return right; }
  if (left.first <= right.first) { return left; }
  return right;
}

struct SegmentTree {
  static const int MAX_DEPTH = 16;
  static const int SIZE = 1 << (MAX_DEPTH + 1);  // 2^18 = 262144

  Node data[SIZE];
  void change(int index, Node value) {
    int target = (1 << MAX_DEPTH) + index;
    data[target] = value;
    for (int i = 1; i <= MAX_DEPTH; i++) {
      target >>= 1;
      data[target] = Merge(data[target * 2], data[target * 2 + 1]);
    }
  }
  Node get(int left, int right) {
    assert(left <= right);
    return in_get(0, 1, left, right);
  }
private:
  Node in_get(int depth, int node, int left, int right) {
    int width = 1 << (MAX_DEPTH - depth);
    int index = node - (1 << depth);
    int node_left = index * width;
    int node_mid = node_left + (width >> 1);
    if (right - left + 1 == width && left == node_left) {
      return data[node];
    } else if (right < node_mid) {
      return in_get(depth + 1, node * 2, left, right);
    } else if (left >= node_mid) {
      return in_get(depth + 1, node * 2 + 1, left, right);
    }
    return Merge(in_get(depth + 1, node * 2, left, node_mid - 1), in_get(depth + 1, node * 2 + 1, node_mid, right));
  }
};


int n, d;
int min_index;
SegmentTree stree;
pair<int, int> seq[60000];
int firsts[60000];
bool visit[60000];
bool need[60000];
map<int, vector<int> > same_seconds;
map<pair<int, int>, int> index_map;
queue<int> use;
bool finish;

int find_min_second(int index) {
  int v = seq[index].first + d;
  int last_index = upper_bound(firsts, firsts + n, v) - firsts;
  assert(seq[index].first + d < seq[last_index].first);
  assert(seq[index].first + d >= seq[last_index - 1].first);
  return stree.get(0, last_index - 1).index;
}

int bfs(int start) {
  int ret = 0;
  queue<int> que;
  que.push(start);
  visit[start] = true;
  stree.change(start, Node(start, INF, INF));
  while (!que.empty()) {
    int index = que.front();
    que.pop();
    use.push(index);
    ret++;
    if (need[index]) { finish = true; }
    while (true) {
      while (visit[min_index]) { min_index++; }
      if (min_index == n) { break; }
      if (firsts[index] - firsts[min_index] <= d) { break; }
      visit[min_index] = true;
      stree.change(min_index, Node(min_index, INF, INF));
      que.push(min_index);
      min_index++;
    }
    while (true) {
      int next = find_min_second(index);
      if (visit[next] || seq[next].second >= seq[index].second) { break; }
      assert(firsts[next] <= d + firsts[index]);
      visit[next] = true;
      stree.change(next, Node(next, INF, INF));
      que.push(next);
    }
  }
  return ret;
}

int main() {
  while (scanf("%d %d", &n, &d) > 0) {
    min_index = 0;
    stree = SegmentTree();
    MEMSET(visit, false);
    MEMSET(need, false);
    same_seconds.clear();
    index_map.clear();
    use = queue<int>();
    finish = false;
    REP(i, n) {
      int v = scanf("%d %d", &seq[i].first, &seq[i].second);
      assert(v == 2);
    }
    sort(seq, seq + n);
    REP(i, n) {
      firsts[i] = seq[i].first;
      stree.change(i, Node(i, seq[i].first, seq[i].second));
      index_map[seq[i]] = i;
      same_seconds[seq[i].second].push_back(seq[i].first);
    }
    FORIT(it, same_seconds) {
      sort(it->second.begin(), it->second.end());
    }
    seq[n] = make_pair(INF, INF);
    firsts[n] = INF;

    int ans = 0;
    while (true) {
      while (visit[min_index]) { min_index++; }
      if (min_index == n) { break; }
      int s = find_min_second(min_index);
      ans += bfs(s);
      // break;
      if (finish) { break; }
      while (!use.empty()) {
        int from = use.front();
        use.pop();
        int first = seq[from].first;
        int second = seq[from].second;
        vector<int> &vec = same_seconds[second];
        vector<int>::iterator it = upper_bound(vec.begin(), vec.end(), first + d);
        it--;
        int to = index_map[make_pair(*it, second)];
        if (visit[to]) { goto END; }
        need[to] = true;
      }
    }
END:
    printf("%d\n", ans);
  }
}