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
#include <bits/stdc++.h>
#define ll long long
#define nd second
#define st first
#define mk std::make_pair
#define debug if(0)

const int MOD = 1e9+7;
const int MAX_N = 3e5;

int v[MAX_N+3];
int radius[MAX_N+3];
int n;

int dp[MAX_N+3];

std::vector<std::pair<int, int> > ranges;

std::vector<int> V[MAX_N+3];

void input() {
    std::cin >> n;
    for (int i = 1; i <= n; i++) 
        std::cin >> v[i] >> radius[i];
}

void find_ranges() {
    for (int i = 1; i <= n; i++) {
        int x = i;
        int y = i;
        int l = v[i] - radius[i];
        int r = v[i] + radius[i];
        while (1) {
            if (y < n && v[y+1] <= r) {
                // przedluzam w prawo
                y++;
                r = std::max(r, v[y] + radius[y]);
                l = std::min(l, v[y] - radius[y]);
            } else if (x > 1 && v[x-1] >= l) {
                x--;
                r = std::max(r, v[x] + radius[x]);
                l = std::min(l, v[x] - radius[x]);
            } else
                break;
        }
        ranges.push_back(mk(x, y));
    }
    debug {
        std::cout << "przedzialy:\n";
        for (auto x: ranges) {
            std::cout << x.st << ", " << x.nd << "\n";
        }
    }
}

bool cmp1(const std::pair<int, int> &a, const std::pair<int, int> &b) {
    return a.nd > b.nd;
}

void count_dp() {
    // dp[i] - ile roznych sum przedzialow na prefiksie i
    std::sort(ranges.begin(), ranges.end(), cmp1);
    dp[0] = 1;
    std::stack<int> stack;
    for (int i = 1; i <= n; i++) {
        while (!ranges.empty() && ranges.back().nd <= i) {
            V[ranges.back().st].push_back(ranges.back().nd);
            ranges.pop_back();
        }
        dp[i] = dp[i-1];
        while (!stack.empty())
            stack.pop();
        for (int j = i; j >= 1; j--) {
            stack.push(j);
            for (auto R: V[j]) {
                // jest przedzial [j, R]
                debug std::cout << "Dorzucam przedzial [" << j << ", " << R << "]\n";

                while (!stack.empty() && stack.top() <= R) 
                    stack.pop();
                if (stack.empty())
                    break;
            }
            if (stack.empty()) {
                // pokrylismy wszystko w przedziale [j, i]
                debug std::cout << "Pokrylismy przedzial [" << j << ", " << i << "]\n";
                if (j == 1) 
                    dp[i] = (dp[i] + 1) % MOD;
                else {
                    // chce zeby j-1 nie byl pokryty, wiec dodaje dp[j-2]
                    dp[i] = (dp[i] + dp[j-2]) % MOD;
                }
            }
        }
        debug std::cout << "dp[" << i << "] = " << dp[i] << "\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(0); std::cin.tie(NULL);
    input();
    find_ranges();
    count_dp();
    std::cout << dp[n] << "\n";
}