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
//miny
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int liczba_min = 300010;
long long adres [liczba_min];
long long range [liczba_min];
long long combin[liczba_min];
int last_non_det [liczba_min];
int new_in_range[liczba_min], in_range_pointer;
int a;

int last_not_detoned(long long int zasieg, int i){
    for(; zasieg <= adres[i]; i--){
        if(adres[i]-range[i] < zasieg) zasieg = adres[i]-range[i];
    }
    return i;
}

long long back_detonations(long long int my_adress, int k){
    long long kombinacja = 0;
    for(int i=0; i<in_range_pointer; i++){
        if(adres[new_in_range[i]] + range[new_in_range[i]] >= my_adress){
            kombinacja = kombinacja - combin[new_in_range[i]] + combin[last_non_det[new_in_range[i]]];
        }
        else{
            new_in_range[i] = new_in_range[in_range_pointer-1];
            new_in_range[in_range_pointer-1] = 0;
            i--, in_range_pointer--;
        }
    }
    new_in_range[in_range_pointer] = k;
    in_range_pointer++;
    return kombinacja;
}

bool wzajemne(int adres_niedet, int i){
    for(; adres_niedet < i; adres_niedet++){
        if(adres[adres_niedet]+range[adres_niedet]>=adres[i]) return true;
    }
    return false;
}

int main() {
    cin>>a;
    long long kombinacja = 0;
    int ostatnia_niedet = 0;
    adres[0] = -2000000000000000000;
    range[0] = 0;
    combin[0] = 1;
    for(int i=1; i<=a; i++){
        kombinacja = 0;
        ostatnia_niedet = i-1;
        cin>>adres[i]>>range[i];
        kombinacja = combin[i-1] + back_detonations(adres[i], i);
        for(; adres[i]-range[i] <= adres[ostatnia_niedet] && ostatnia_niedet != 0; ostatnia_niedet--);
        if(wzajemne(ostatnia_niedet+1, i)){
            combin[i] = combin[i-1];
        }
        else{
            combin[i] = kombinacja + combin[last_not_detoned(adres[i]-range[i], i-1)];
        }
        last_non_det[i] = last_not_detoned(adres[i]-range[i], i-1);
        combin[i] = combin[i] % 1000000007;
    }
    cout<<combin[a]<<endl;
    return 0;
}