# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1111322 | onlk97 | Road Construction (JOI21_road_construction) | C++14 | 3973 ms | 28964 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define x first
#define y second
#define pb push_back
using namespace std;
using namespace __gnu_pbds;
using pii=pair <int,int>;
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n,k;
cin>>n>>k;
pii a[n+1];
for (int i=1; i<=n; i++){
int u,v; cin>>u>>v;
a[i]={u-v,u+v};
}
sort(a+1,a+n+1);
int l=1,r=4e9;
tree <pii,null_type,less <pii>,rb_tree_tag,tree_order_statistics_node_update> s;
while (l<r){
int mid=(l+r)/2;
s.clear();
int cnt=0,lst=1;
for (int i=1; i<=n; i++){
while (lst<i&&a[lst].x<a[i].x-mid){
s.erase({a[lst].y,lst});
lst++;
}
cnt+=s.order_of_key({a[i].y+mid+1,0})-s.order_of_key({a[i].y-mid,0});
s.insert({a[i].y,i});
}
if (cnt>=k) r=mid;
else l=mid+1;
}
l--;
vector <int> vec;
s.clear();
int lst=1;
for (int i=1; i<=n; i++){
while (lst<i&&a[lst].x<a[i].x-l){
s.erase({a[lst].y,lst});
lst++;
}
int idx=s.order_of_key({a[i].y-l,0});
while (idx<s.size()){
pii tp=*s.find_by_order(idx);
if (tp.x>a[i].y+l) break;
vec.pb(max(a[i].x-a[tp.y].x,abs(a[i].y-tp.x)));
idx++;
}
s.insert({a[i].y,i});
}
sort(vec.begin(),vec.end());
while (vec.size()<k) vec.pb(l+1);
for (int i:vec) cout<<i<<'\n';
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |