Submission #1040989

#TimeUsernameProblemLanguageResultExecution timeMemory
1040989alexddRoad Construction (JOI21_road_construction)C++17
0 / 100
10065 ms2097152 KiB
#include<bits/stdc++.h> using namespace std; #define int long long const int INF = 1e9; int n,cate; pair<int,int> v[250005]; pair<int,int> p[250005]; vector<int> sol; int afis(int lim) { sol.clear(); int poz=1; set<pair<int,int>> s; for(int i=1;i<=n;i++) { while(p[i].first-p[poz].first>lim) { s.erase({p[poz].second,poz}); poz++; } auto it = s.lower_bound({p[i].second-lim,-1}); while(it!=s.end()) { if((*it).first > p[i].second+lim) break; sol.push_back(max(abs(p[i].first-p[(*it).second].first),abs(p[i].second-p[(*it).second].second))); it++; } s.insert({p[i].second,i}); } return sol.size(); } signed main() { ios_base::sync_with_stdio(0);cin.tie(0); int k; cin>>n>>k; for(int i=1;i<=n;i++) { cin>>v[i].first>>v[i].second; p[i].first = v[i].first + v[i].second; p[i].second = v[i].first - v[i].second; } sort(p+1,p+1+n); int st=0,dr=INF,ans=0; while(st<=dr) { int mij=(st+dr)/2; if(afis(mij)<=k) { ans=mij; st=mij+1; } else dr=mij-1; } afis(ans); sort(sol.begin(),sol.end()); for(auto x:sol) cout<<x<<"\n"; for(int i=1;i<=k-afis(ans);i++) cout<<ans+1<<"\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...