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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct punkt {
	int64_t x;
	int typ;
	int id;

	bool operator< (const struct punkt& par) {
		if (x == par.x) {
			return (typ < par.typ);
		}
		return x < par.x;
	}
};

struct mina{
	int64_t p;
	int64_t a;
};

#define MOD 1000000007L

#define DUMP do {	\
	cout << "i=" << i << "; x=" << p[i].x << "; typ=" << p[i].typ << "; id=" << p[i].id << "; A=" << A << "; N=" << N << "; ac=" << ac << "; pc=" << pc << "\n"; \
} while(0);	\

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio (false);
	int n, i, ac, pc;
	int64_t a, r, A=0, N=1, NA;
	cin >> n;
	vector<mina> m(n);
	vector<punkt> p(n*3);
	vector<int> akt(n);
	vector<int> pod(n);
	vector<int64_t> pods(n);
	int podc = 0;
	ac = 0;
	pc = 0;
	for (i = 0; i < n; ++i) {
		cin >> a >> r;
		m[i].p = m[i].a = -1;
		p[3*i+0] = punkt{a-r, 1, i};
		p[3*i+1] = punkt{a, 2, i};
		p[3*i+2] = punkt{a+r, 3, i};
	}
	sort(p.begin(), p.end());
	for (i = 0; i < 3*n; ++i) {
		switch(p[i].typ) {
			case 1:
//				pod[pc++] = p[i].id;
				m[p[i].id].p = 0;
				podc++;
				break;
			case 2:
				if(m[p[i].id].p >= 0 && pc > 0) {
//					A = m[p[i].id].p;
					A = pods[--pc];
				} else {
					A = (A + N) % MOD;
				}
				m[p[i].id].p = -1;
				podc--;
//				while(pc > 0 && m[pod[pc-1]].p < 0)
//					pc--;
//				if (pc > 0) {
//					m[pod[pc-1]].p = (m[pod[pc-1]].p + A) % MOD;
//				}
				if (podc > 0) {
					pods[pc++] = A;
				}
				akt[ac++] = p[i].id;
				m[p[i].id].a = A;
				break;
			case 3:
				m[p[i].id].a = -1;
				while(ac > 0 && m[akt[pc-1]].a < 0)
					ac--;
				NA=0;
				if (ac > 0) {
					NA=m[akt[pc-1]].a;
				}
				N=(N+A-NA)% MOD;
				A=NA;
				break;
		}
//		DUMP

	}

	cout << N << "\n";
}