1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <cstdio>
#include <vector>

using namespace std;

typedef long long LL;

const int p = 1000000007;

int tsize;
vector<int> tree;
const int MAX = p;

int minof(int p, int a, int b, int A, int B) {
  if (b <= A || B <= a) return MAX;
  if (a <= A && B <= b) return tree[p];
  int C = (A+B)/2;
  return min(minof(p*2, a, b, A, C), minof(p*2+1, a, b, C, B)); 
}

int minof(int a, int b) {
  return minof(1, a, b, 0, tsize);
}

void insert(int a, int v) {
  a += tsize;
  tree[a] = v;
  a /= 2;
  while (a > 0) {
    tree[a] = min(tree[a*2], tree[a*2+1]);
    a /= 2;
  }
}

int main() {
  int n; scanf("%d", &n);
  vector<LL> a(n), r(n);
  for (int i=0; i<n; ++i) {
    scanf("%lld %lld\n", &a[i], &r[i]);
  }

  vector<LL> zero(n), one(n), any(n);
  vector<int> stack;
  tsize = 1;
  while (tsize < n) tsize *= 2;
  tree = vector<int>(tsize * 2, n+1);

  zero[0] = 1;
  one[0] = 1;
  any[0] = 2;
  stack.push_back(0);
  insert(0, 0);

  for (int i=1; i<n; ++i) {
//    printf("Computing for %d:\n", i);

    int it = lower_bound(&a[0], &a[i], a[i] - r[i]) - &a[0];
    if (it < i) {
      it = minof(it, i); 
    }
    insert(i, it);
    if (it == 0) {
//      printf("Crashing everything\n");
      one[i] = 1; 
    } else {
//      printf("Last no crash: %d\n", it-1);
      one[i] = any[it-1];
    }

    while (!stack.empty() && a[stack.back()] + r[stack.back()] < a[i]) {
      stack.pop_back();
    }
    
    if (stack.empty()) {
//      printf("Nobody killing me\n");
      zero[i] = any[i-1];
    } else {
//      printf("Killed by: %d\n", stack.back());
      zero[i] = (p + any[i-1] - one[stack.back()]) % p;
    }

    any[i] = (zero[i] + one[i]) % p;
  
//    printf("Got: %d %d %d\n", zero[i], one[i], any[i]);

    stack.push_back(i);
  }

  printf("%d\n", any[n-1]);
  return 0;
}