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
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <algorithm>
#include <cstdio>
using namespace std;

const long long mod = 1000000007;
const int MAX_N = 300007, inf = 999999999;

//------trees-------
const int leafCount = 1 << 19;
int tree[2][leafCount << 1];
void insertMin(int x, int value) {
    x += leafCount;
    tree[0][x] = value;
    while(x > 1) {
        x >>= 1;
        tree[0][x] = min(tree[0][x << 1], tree[0][(x << 1) + 1]);
    }
}
int getMin(int a, int b) {
    a += leafCount; b += leafCount;
    int result = min(tree[0][a], tree[0][b]);
    while((a >> 1) != (b >> 1)) {
        if(!(a & 1))
            result = min(result, tree[0][a + 1]);
        if(b & 1)
            result = min(result, tree[0][b - 1]);
        a >>= 1;
        b >>= 1;
    }
    return result;
}
void insertMax(int a, int b, int value) {
    a += leafCount; b += leafCount;
    tree[1][a] = max(tree[1][a], value);
    tree[1][b] = max(tree[1][b], value);
    while((a >> 1) != (b >> 1)) {
        if(!(a & 1))
            tree[1][a + 1] = max(tree[1][a + 1], value);
        if(b & 1)
            tree[1][b - 1] = max(tree[1][b - 1], value);
        a >>= 1;
        b >>= 1;
    }
}
int GetMax(int x) {
    x += leafCount;
    int result = tree[1][x];
    while(x > 1) {
        x >>= 1;
        result = max(result, tree[1][x]);
    }
    return result;
}

//------------

long long n, a[MAX_N], r[MAX_N], dp[2][MAX_N];
int lastLeft[MAX_N], firstLeft[MAX_N];

int FindLastRight(int x) {
    int beg = x, end = n - 1;
    while(beg <= end) {
        int mid = (beg + end) >> 1;
        if(a[mid] <= a[x] + r[x])
            beg = mid + 1;
        else
            end = mid - 1;
    }
    return beg - 1;
}

int FindLastLeft(int x) {
    int beg = 0, end = x;
    while(beg <= end) {
        int mid = (beg + end) >> 1;
        if(a[mid] < a[x] - r[x])
            beg = mid + 1;
        else
            end = mid - 1;
    }
    return beg == x ? x : getMin(beg, x - 1);
}

int main() {
    fill(tree[0], tree[0] + (leafCount << 1), inf);
    fill(tree[1], tree[1] + (leafCount << 1), -1);
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%lld%lld", &a[i], &r[i]);
        lastLeft[i] = FindLastLeft(i);
        insertMin(i, lastLeft[i]);
    } 
    for(int i = 0; i < n; i++) {
        firstLeft[i] = GetMax(i);
        if(firstLeft[i] == -1)
            firstLeft[i] = i;
        insertMax(i, FindLastRight(i), i);
    }
    dp[0][0] = dp[1][0] = 1;
    for(int i = 1; i < n; i++) {
        int l = lastLeft[i], f = firstLeft[i];
        dp[0][i] = (dp[0][i - 1] + dp[1][i - 1] - dp[1][f] + mod) % mod; //if f == i then dp[1][f] = 0
        dp[1][i] = ((l == 0) ? 1 : dp[1][l - 1] + dp[0][l - 1]) % mod;
    }
    printf("%d\n", dp[0][n - 1] + dp[1][n - 1]);
    return 0;
}

/*
4 
0 2
2 0
3 2
7 4
*/