Submission #1041042

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