Submission #1798838


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() or it->first>=r) break;
            l=it->first;
            if(it->second>=r){
                rec(to_index[*it]);
                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

Submission Time
Task K - ターゲット
User walkre
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2054 Byte
Status WA
Exec Time 101 ms
Memory 24960 KB

Judge Result

Set Name All
Score / Max Score 0 / 5
Status
AC × 4
WA × 6
Set Name Test Cases
All 00, 01, 02, 03, 04, 05, 06, 07, 90, 91
Case Name Status Exec Time Memory
00 WA 99 ms 24960 KB
01 WA 100 ms 24960 KB
02 WA 101 ms 24960 KB
03 WA 79 ms 21632 KB
04 WA 79 ms 21760 KB
05 WA 78 ms 21632 KB
06 AC 87 ms 24960 KB
07 AC 86 ms 24960 KB
90 AC 1 ms 256 KB
91 AC 1 ms 256 KB