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
#include <bits/stdc++.h>
using namespace std;
typedef set<unsigned long long>::iterator iy;
int a,raz[300001],pol[300001],odp,pomox;
vector<int>minen[3000];
set<unsigned long long>odpowiedzi;
unsigned long long akto,dosp; 
int mamy[3001];
unsigned long long dwa[3001];
bool juzdodalem[100][100];
void dynamik(int ter)
{    
    iy it=odpowiedzi.lower_bound(akto);
    if(it==odpowiedzi.end())
    {
        ++odp;
        odpowiedzi.insert(akto);
    }
    else
    {
        dosp=*it;
        if(akto!=dosp)
        {
            ++odp;
            odpowiedzi.insert(akto);
        }
    }
    if(ter!=a-1)
    dynamik(ter+1);
    for(int i=0;i<minen[ter].size();++i)
    {
        if(mamy[minen[ter][i]]==0)
        {
            akto+=dwa[minen[ter][i]];
        }
        mamy[minen[ter][i]]++;
    }
    it=odpowiedzi.lower_bound(akto);
    if(it==odpowiedzi.end())
    {
        ++odp;
        odpowiedzi.insert(akto);
    }
    else
    {
        dosp=*it;
        if(akto!=dosp)
        {
            ++odp;
            odpowiedzi.insert(akto);
        }
    }
    if(ter!=a-1)
    dynamik(ter+1);
    for(int i=0;i<minen[ter].size();++i)
    {
        mamy[minen[ter][i]]--;
        if(mamy[minen[ter][i]]==0)
        {
            akto-=dwa[minen[ter][i]];
        }  
    }
    
}
void dfs(int ter,int dotego)
{
    for(int i=0;i<minen[ter].size();++i)
    {
        if(juzdodalem[dotego][minen[ter][i]]==0)
        {
            juzdodalem[dotego][minen[ter][i]]=1;
            minen[dotego].push_back(minen[ter][i]);
            dfs(minen[ter][i],dotego);
        }
    }
}
int main()
{
    scanf("%d",&a);
    if(a>35)
    {
        printf("%d",1);
        return 0;
    }
    dwa[0]=1;
    for(int i=1;i<64;++i)
    dwa[i]=dwa[i-1]*2;

    for(int i=0;i<a;++i)
    {
        minen[i].push_back(i);
        scanf("%d%d",&pol[i],&raz[i]);
        for(int j=i-1;j>=0;--j)
        {
            if(pol[i]-raz[i]<=pol[j])
            {
                minen[i].push_back(j);
                juzdodalem[i][j]=1;
            }
            if(pol[j]+raz[j]>=pol[i])
            {
                minen[j].push_back(i);
                juzdodalem[j][i]=1;
            }
        }
    }
    for(int i=0;i<a;++i)
    {
        pomox=minen[i].size();
        for(int j=0;j<pomox;++j)
        {
            dfs(minen[i][j],i);
        }
    }
    dynamik(0);
    printf("%d",odp);  
    return 0;
}