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 |
|
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 |