Submission #1798837

---

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;
    });

    set<pair<int,int>> lr;
    map<pair<int,int>,int> to_index;
    rep(i,0,N){
        lr.insert(make_pair(xr[i].first-xr[i].second,xr[i].first+xr[i].second));
        to_index[make_pair(xr[i].first-xr[i].second,xr[i].first+xr[i].second)]=i;
    }

    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;
        lr.erase(make_pair(l,r));
        for(;;){
            auto it=lr.upper_bound(make_pair(l,inf));
            if(it==lr.end()) break;
            if(it->first>=r){
                rec(to_index[*it]);
                continue;
            }
            l=it->first;
            if(it->second>=r) continue;
            res=max(res,rec(to_index[*it])+1);
        }

        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