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
#include <cstdio>
#include <vector>
using namespace std;
const long long modulo = 1000000007;

struct mina {
	long long loc;
	long long maxrange;
	long long w;
	long long s;
	
	mina(long long l, long long m, long long w, long long s): loc(l), maxrange(m), w(w), s(s) {}
};

vector<mina> mines;

int main() {
	long long n, a, b;
	long long result = 0;
	long long independent_mines = 1;
	scanf("%lld", &n);
	if (n == 0) {
		printf("1\n");
		return 0;
	}
	scanf("%lld %lld", &a, &b);
	// printf("MINE %lld %lld\n", a, b);
	
	mines.push_back(mina(a, a+b, 2, 1));
	result = 2;
	
	for(int i = 1; i < n; ++i){
		scanf("%lld %lld", &a, &b);
		// printf("MINE %lld %lld\n", a, b);
		long long c_idx = independent_mines - 1;
		long long leftrange = a - b;
		// printf("c+idx: %lld\n", c_idx);
		long long new_maxrange = a+b;
		while(c_idx >= 0){
			if (mines[c_idx].loc < leftrange) {
				break;
			}
			// mine c_idx is in leftrange
			long long ml = mines[c_idx].maxrange;
			if (ml >= a) {
				// printf("Merging %lld with %lld\n", a, mines[c_idx].loc);
				// we can merge mines
				// printf("Merging\n");
				mines.erase(mines.begin()+c_idx);
				independent_mines--;
				// printf("%lld mines remaining\n", independent_mines);
				new_maxrange = max(ml, a+b);
			}
			c_idx--;
		}
		// printf("Afterloop\n");
		mines.push_back(mina(a, new_maxrange, 2, 1));
		independent_mines++;
		long long k = c_idx+1; // furthest mine in our leftrange
		long long x = -1; // first mine that has us in its rightrange
		for (int j = 0; j < k; ++j) {
			long long ml = mines[c_idx].maxrange;
			if (ml >= a) {
				x = j;
				break;
			}			
		}
		// need to calculate new values
		long long y = independent_mines - 2; // previous mine idx
		 // printf("x: %lld, y: %lld, k: %lld\n", x, y, k);
		long long new_w = 0;
		long long new_s = 0;
		if (x == -1) {
			new_w = mines[y].w + mines[k].s % modulo;
			new_s = mines[k].s;				
		} else {
			new_w = mines[y].w + mines[k-1].w - mines[x].s % modulo;
			new_s = mines[x].w;
		}
		mines[y+1].w = new_w;
		mines[y+1].s = new_s;
		result = new_w;
	}
	//printf("\n");
	//  for (unsigned int i = 0; i < mines.size(); ++i){
	//  	printf("w: %lld, s: %lld\n", mines[i].w, mines[i].s);
	//  }
	
	printf("%lld\n", result);
}