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