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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
using D = double;
#define f1 first
#define f2 second
#define randint(a, b) uniform_int_distribution<int>{a, b}(gen)
#ifdef LOC
void OUT() {cout << '\n';}
template<class H, class ... T> void OUT(H h, T ... t)
{
	cout << h << ' ';
	OUT(t...);
}
#define P(...) cout << "[" << #__VA_ARGS__ << "] ", OUT(__VA_ARGS__)
#else
#define P(...)
#define OUT(...)
#endif
//mt19937 gen;
LL pos[300100];
LL siz[300100];

int tree[1<<20];
int depth = 4;
int MMOD = 1e9 + 7;

LL fins[20][300100];

inline int add(int a, int b)
{
	a += b;
	if(a >= MMOD) a -= MMOD;
	return a;
}

void update(int p)
{
	while(p > 1)
	{
		p /= 2;
		tree[p] = add(tree[2 * p], tree[2 * p + 1]);
	}
}

int getsum(int st, int en, int a = 0, int b = depth - 1, int p = 1)
{
	if(st <= a && b <= en) return tree[p];
	if(en < a || b < st) return 0;
	return add(
			getsum(st, en, a, (a+b)/2, p * 2),
			getsum(st, en, (a+b)/2 + 1, b, p * 2 + 1)
			);
}

LL getmax(int a, int b)
{
	if(a > b) return 0;
	int k = (b - a + 1);
	k = __lg(k);
	return max(fins[k][a], fins[k][b - (1<<k) + 1]);
}
#ifdef LOC
void pr()
{
	for(int i = 1; i < 2 * depth; ++i) cout << tree[i] << ' ';
	cout << '\n';
}
#else
void pr() {}
#endif

int getIntervalEnd(int posNow, LL val)
{
	int st = 1, en = posNow, s;
	while(st < en)
	{
		s = (st + en) / 2;
		if(getmax(s, posNow - 1) < val)
		{
			en = s;
		}
		else
		{
			st = s + 1;
		}
	}
	OUT("Binsearch returned: ", st - 1);
	return st - 1;
}
vector<int> nonzeroed;
int n;
int main(int, char ** /*args*/)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	while(n + 3 >= depth) depth *= 2;
	for(int i = 1; i <= n; ++i)
	{
		cin >> pos[i] >> siz[i];
		fins[0][i] = pos[i] + siz[i];
	}
	fins[0][0] = -1e18;
	///Robimy na przedziale <0, n>, nie <0, n)
	for(int j = 1; (1<<(j-1)) <= n; ++j)
	{
		for(int i = 0; i + (1<<(j-1)) <= n; ++i)
		{
			fins[j][i] = max(fins[j - 1][i], fins[j - 1][i + (1<<(j - 1))]);
		}
	}
	tree[depth + 0] = 1;
	update(depth + 0);
	for(int i = 1; i <= n; ++i)
	{
		P(i);
		tree[depth + i] = getsum(getIntervalEnd(i, pos[i]), i - 1);
		update(depth + i);
		while(nonzeroed.size() > 0)
		{
			if(pos[i] - siz[i] <= pos[nonzeroed.back()])
			{
				tree[depth + nonzeroed.back()] = 0;
				update(depth + nonzeroed.back());

				P(nonzeroed.back());
				nonzeroed.pop_back();
			}
			else break;
			///Try pop, if fails break
		}
		nonzeroed.push_back(i);
		pr();
	}
	cout << tree[1] << '\n';
	return 0;
}