Submission #1296096

#TimeUsernameProblemLanguageResultExecution timeMemory
1296096nathako9nLightning Rod (NOI18_lightningrod)C++20
7 / 100
1100 ms156256 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...