#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if(!(cin >> n)) return 0;
vector<pair<ll,ll>> ar;
ar.reserve(n);
for(int i=0;i<n;i++){
ll x,y; cin >> x >> y;
ar.emplace_back(x+y, x-y);
}
sort(ar.begin(), ar.end(), greater<pair<ll,ll>>());
vector<ll> tail;
int i = 0;
while(i < n){
int j = i;
while(j < n && ar[j].first == ar[i].first) ++j;
int oldSize = (int)tail.size();
vector<pair<int,ll>> updates;
updates.reserve(j - i);
for(int k = i; k < j; ++k){
ll val = - ar[k].second;
int pos = int(lower_bound(tail.begin(), tail.end(), val) - tail.begin());
updates.emplace_back(pos, val);
}
if(!updates.empty()){
unordered_map<int,ll> best;
best.reserve(updates.size()*2);
for(auto &p : updates){
int pos = p.first;
ll v = p.second;
auto it = best.find(pos);
if(it==best.end()) best[pos]=v;
else if(v < it->second) it->second = v;
}
for(auto &kv : best){
int pos = kv.first;
ll v = kv.second;
if(pos < oldSize){
if(v < tail[pos]) tail[pos] = v;
}
}
auto itNew = best.find(oldSize);
if(itNew != best.end()){
tail.push_back(itNew->second);
}
}
i = j;
}
cout << tail.size() << '\n';
return 0;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |