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
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

const int Q = ((int)1e9) + 7;

void dod(int &x, int y) {
  x += y;
	if (x >= Q) x -= Q;
}

long long koduj(long long M, int ost1, int wym0) {
	return M * ost1 + wym0;
}

vector<int> vb,ve;

int main() {
  int n;
	scanf("%d",&n);
	vector<long long> a(n), r(n);
	vb = ve = vector<int>(n+1);
	for (int i = 0; i < n; i++) {
		scanf("%lld %lld",&a[i],&r[i]);
	}
	for (int i = 0; i < n; i++) {
	  vb[i] = lower_bound(a.begin(), a.end(), a[i]-r[i]) - a.begin();
	  ve[i] = upper_bound(a.begin(), a.end(), a[i]+r[i]) - a.begin() - 1;
	}
	vb[n]=0;

	vector<int> kan(n+1), pr(n), s;

	kan[n] = n;
	s.push_back(n);
	for(int i = n-1; i >= 0; i--) {
	  while(vb[s.back()] > i) s.pop_back();
		pr[i] = s.back();
		s.push_back(i);
	}

	s.clear();
	for (int i = n-1; i >= 0; i--) {
	  while(!s.empty() && a[s.back()]-r[s.back()] >= a[i]-r[i]) s.pop_back();
		kan[i] = i;
		if (!s.empty() && a[s.back()] <= a[i]+r[i]) kan[i] = s.back();
		s.push_back(i);
	}

	for(int i = 0; i < n; i++) {
	//	printf("%d:: vb=%d, ve=%d pr=%d kan=%d\n", i, vb[i], ve[i], pr[i], kan[i]);
	}

	const int M = n+5;
	map<long long, int> dp,e;
	dp[koduj(M, 0, n)] = 1;

	for (int i = 0; i < n; i++) {
		e.clear();
	  for (map<long long, int>::iterator it = dp.begin(); it != dp.end(); ++it) {
			int ost1 = it->first / M;
			int wym0 = it->first % M;
//			printf("%d :: %d %d %d\n", i, ost1, wym0, it->second);
			if (ost1 <= i) {
				// wez 0
				dod(e[koduj(M, i+1, wym0 == i ? kan[pr[i]] : std::min(wym0, kan[pr[i]]))], it->second);
			}
			if (wym0 > i) {
 				// wez 1
				dod(e[koduj(M, std::max(ost1, ve[i]+1), wym0)], it->second);
			}
		}
		dp = e;
	}

	 //printf("%d\n", (int)dp.size());
	printf("%d\n", dp[koduj(M, n, n)]);
	return 0;
}