Submission #4025125

---

Source Code Expand

#include<cstdio>
#include<bits/stdc++.h>
typedef long long int ll;
#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOR_IN(i, a, b) for(int i = (a); i < (b); i++)
#define BETWEEN(x, a, b) ((x) >= (a) && (x) <= (b))
#define LOG(...) fprintf(stderr, __VA_ARGS__)
#define INF 200000001
using namespace std;

/*
n
x1 r1
...
xn rn

n 100000
xi 100000000
ri 100000000
 */
typedef pair<int,int> pp;
int n;
pp circ[100000];

int main(){
  cin >> n;
  REP(i,n){
    int x,r;
    cin >> x >> r;
    circ[i] = make_pair(x-r,x+r);
  }

  sort(circ, circ + n);
  reverse(circ, circ + n);  

  vector<int> dp(n,INF);
  REP(i,n){
    *lower_bound(dp.begin(), dp.end(), circ[i].second) = circ[i].second;
  }

  cout << (lower_bound(dp.begin(), dp.end(), INF) - dp.begin()) << endl;
  return 0;
}

Submission Info

Judge Result