Submission #1798822

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

using i64=int64_t;

#define rep(i,x,y) for(i64 i=i64(x),i##_max_for_repmacro=i64(y); i<i##_max_for_repmacro; ++i)
#define debug(x) #x << "=" << (x)
 
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif
 
const int inf=1.01e9;
const i64 inf64=4.01e18;
const double eps=1e-9;
 
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
        os << v << ",";
    }
    os << "]";
    return os;
}

void solve(){
    int N;
    cin >> N;

    vector<pair<int,int>> xr(N);
    rep(i,0,N) cin >> xr[i].first >> xr[i].second;
    
    sort(begin(xr),end(xr),[](pair<int,int> &a,pair<int,int> &b){
        return a.first-a.second<b.first-b.second;   
    });

    vector<int> ls(N);
    rep(i,0,N) ls[i]=xr[i].first-xr[i].second;

    static int dp[100000];
    static bool done[1000000];
    function<int(int)> rec=[&](int i){
        int& res=dp[i];
        if(done[i]) return res;
        done[i]=true;

        res=1;
        int l=xr[i].first-xr[i].second,r=xr[i].first+xr[i].second;
        for(;;){
            int j=upper_bound(begin(ls),end(ls),l)-begin(ls);
            if(j==N or ls[j]>=r) break;
            if(xr[j].first+xr[j].second>=r){
                l=ls[j];
                continue;
            }
            res=max(res,rec(j)+1);
            l=ls[j];
        }

        return res;
    };

    int ans=0;
    rep(i,0,N) ans=max(ans,rec(i));

    cout << ans << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}

Submission Info

Judge Result