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
#include <bits/stdc++.h>
#define IOSTREAM_BOOST true
using namespace std;

int n;
vector<pair<int, int>> mines;
int detonated[40];

set<int> results;

int main()
{
    #if IOSTREAM_BOOST
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    #endif
    
    cin >> n;
    for(int i = 0; i < n; i++){
        int a, b;
        cin >> a >> b;
        mines.push_back({a, b});
    }
    for(int i = 0; i < n; i++){
        detonated[i] = 0;
        int l = mines[i].first;
        int r = mines[i].first;
        int lptr = i;
        int rptr = i;
        while(true){
            bool flag = false;
            while(lptr >= 0 && mines[lptr].first >= l){
                l = min(l, mines[lptr].first - mines[lptr].second);
                r = max(r, mines[lptr].first + mines[lptr].second);
                detonated[i] |= (1 << lptr);
                lptr--;
                flag = true;
            }
            while(rptr < n && mines[rptr].first <= r){
                l = min(l, mines[rptr].first - mines[rptr].second);
                r = max(r, mines[rptr].first + mines[rptr].second);
                detonated[i] |= (1 << rptr);
                rptr++;
                flag = true;
            }
            if(!flag) break;
        }
    }
    for(int mask = 0; mask < (1 << n); mask++){
        int cmask = 0;
        for(int bit = 0; bit < n; bit++) if(mask & (1 << bit)) cmask |= detonated[bit];
        results.insert(cmask);
    }
    cout << results.size() << "\n";
    return 0;
}