제출 #1036840

#제출 시각아이디문제언어결과실행 시간메모리
1036840alexddRoad Construction (JOI21_road_construction)C++17
32 / 100
10057 ms29252 KiB
#include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef tree<pair<long long,long long>,null_type,less<pair<long long,long long>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; #define int long long const int INF = 5e9; int n; pair<int,int> v[250005]; pair<int,int> p[250005]; int numara(int lim) { for(int i=1;i<=n;i++) { 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 poz=1,cnt=0; ordered_set s; for(int i=1;i<=n;i++) { while(p[i].first-p[poz].first>lim) { s.erase({p[poz].second,poz}); poz++; } s.insert({p[i].second+lim,n+5}); s.insert({p[i].second-lim,-2}); cnt += s.order_of_key({p[i].second+lim,n+5}) - s.order_of_key({p[i].second-lim,-2}) - 1; s.erase({p[i].second+lim,n+5}); s.erase({p[i].second-lim,-2}); s.insert({p[i].second,i}); } return cnt; } void afis(int lim) { for(int i=1;i<=n;i++) { 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 poz=1; set<pair<int,int>> s; vector<int> sol; 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}); } sort(sol.begin(),sol.end()); for(auto x:sol) cout<<x<<"\n"; } 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; } int st=0,dr=INF,ans=0; while(st<=dr) { int mij=(st+dr)/2; if(numara(mij)<=k) { ans=mij; st=mij+1; } else dr=mij-1; } afis(ans); for(int i=1;i<=k-numara(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...