Submission #6421016

---

Source Code Expand

#include <bits/stdc++.h>
#define debug(x) cerr << #x << ": " << x << '\n';
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = (int)1e9;

int N;
P circle[100000];
P dp[100000];

int main(void){
    cin >> N;
    for(int i = 0; i < N; i++){
        int x, r; cin >> x >> r;
        circle[i] = P(x-r, x+r);
    }

    sort(circle, circle + N, [](P a, P b){return (a.second==b.second) ? a.first<b.first : a.second>b.second;});
    for(int i = 0; i < N; i++){
        dp[i] = P(INF, INF);
    }

    // for(int i = 0; i < N; i++) printf("%d, %d\n", circle[i].first, circle[i].second);

    for(int i = 0; i < N; i++){
        *lower_bound(dp, dp + N, circle[i], [](P a, P b){return a.first < b.first;}) = circle[i];
    }

    // for(int i = 0; i < N; i++) printf("%d, %d\n", dp[i].first, dp[i].second);

    cout << lower_bound(dp, dp + N, P(INF, INF)) - dp << '\n';

    return 0;
}

Submission Info

Judge Result