Submission #3012978

---

Source Code Expand

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <iomanip>

#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue

using namespace std;
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
const int inf = 1e9;
const ll linf = 1LL << 50;
int n;
ll x[100001];
ll r[100001];
vector<int> vec;
int dp[100001];

bool comp(const int &a, const int &b){
		return x[a] + r[a] > x[b] + r[b];
}

bool compr(const int &a, const int &b){
		if(x[a] - r[a] != x[b] - r[b])return x[a] - r[a] < x[b] - r[b];
		else return x[a] + r[a] < x[b] + r[b];
}

int main(int argc, char const* argv[])
{
	cin >> n;
	for(int i = 0; i < n; i++){
			cin >> x[i] >> r[i];
			vec.pb(i);
	}
	x[n] = 0;
	r[n] = - linf / 2;
	sort(vec.begin(), vec.end(), compr);
	fill(dp, dp + n + 1, n);
	for(int i = 0; i < n; i++){
			*lower_bound(dp, dp + n + 1, vec[i], comp) = vec[i];
	}
	cout << lower_bound(dp, dp + n + 1, n, comp) - dp << endl;
	return 0;
}

Submission Info

Judge Result