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
#pragma GCC optimize("O3")
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define BOOST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define FOR(a, b, c) for(int a = b; a < c; ++a)
#define PB push_back
#define MP make_pair
#define INF (int)1e9+7
#define LLINF 2e18+7
#define ALL(a) a.begin(), a.end()
#define SIZE(a) (int)a.size()

typedef unsigned long long ULL;
typedef long long LL;
typedef long double LD;

using namespace std;

//#define DEBUG

const LL MOD = 1e9 + 7;
set <pair <int, int> > ranges;

void parse()
{
    LL n;
    cin >> n;

    vector <LL> mines(n);
    vector <LL> radii(n);
    vector <LL> left(n);
    vector <LL> right(n);

    FOR(i, 0, n)
    {
        cin >> mines[i] >> radii[i];
    }

    FOR(i, 0, n)
    {
        auto tmp1 = lower_bound(ALL(mines), mines[i] - radii[i]);
        auto tmp2 = upper_bound(ALL(mines), mines[i] + radii[i]);

        tmp2--;

        left[i] = tmp1 - mines.begin();
        right[i] = tmp2 - mines.begin();
    }

    FOR(i, 0, n)
    {
        left[i] = min(left[i], left[left[i]]);
    }

    for(int i = n - 1; i >= 0; --i)
    {
        right[i] = max(right[i], right[right[i]]);
    }

    FOR(i, 0, n)
    {
        ranges.insert({left[i], right[i]});
    }
}

int main()
{
    #ifndef DEBUG
    BOOST;
    #endif

    parse();

    vector <LL> masks;

    for(auto& r : ranges)
    {
        LL m = 0;

        FOR(i, r.first, r.second + 1)
        {
            m |= (1ll << i);
        }

        masks.PB(m);
    }

    set <LL> res;
    int MAX = min(22, SIZE(masks));

    FOR(mask, 0, (1ll << MAX))
    {
        LL m = 0;

        FOR(i, 0, MAX)
        {
            if(mask & (1ll << i))
                m |= masks[i];
        }

        res.insert(m);
    }

    cout << SIZE(res) << "\n";

    return 0;
}