| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 709977 | alvingogo | Road Construction (JOI21_road_construction) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;
/*
never did before, write down here
we want to find out the minimum k mahhaton dist
transform the (x, y) into (x+y, x-y)
so that |x-a|+|y-b| = max(|x'-a'|,|y'-b'|)
and binary search the k, find how many pair of points dis <= k
actually, it's like:
maintain a single-point-modify-range-query-sum DS
scan one axis, the DS is for another axis, when we want to cal all points whose x' = z
just add the Y to the DS, and count the amount of [Y-k, Y+k],
wow, not that hard, right?
we need to find the 1st to kth smallest distance
find the k-th smallest distance, let it be x
for all dist<x, the sum is small enough so we can iterate all of it
let's go
*/
struct BIT{
int n;
vector<int> bt;
void init(int x){
n=x;
bt.resize(x+1);
}
void update(int x,int y){
x++;
for(;x<=n;x+=(x&-x)){
bt[x]+=y;
}
}
int query(int x){
int ans=0;
x++;
for(;x>0;x-=(x&-x)){
ans+=bt[x];
}
return ans;
}
int ask(int l,int r){
return query(r)-query(l-1);
}
}bt;
signed main(){
AquA;
int n,m;
cin >> n >> m;
vector<pair<int,int> > v;
vector<int> g;
for(int i=0;i<n;i++){
int a,b;
cin >> a >> b;
v.push_back({a+b,a-b});
g.push_back(a-b);
}
sort(v.begin(),v.end());
sort(g.begin(),g.end());
g.erase(unique(g.begin(),g.end()),g.end());
auto lis=[&](int x){
return lower_bound(g.begin(),g.end(),x)-g.begin();
};
bt.init(g.size());
for(auto &h:v){
h.sc=lis(h.sc);
}
auto cal=[&](int k){
int z=0;
int ans=0;
for(int i=0;i<n;i++){
while(z<i && v[z].fs+k<v[i].fs){
bt.update(v[z].sc,-1);
z++;
}
int l=lis(g[v[i].sc]-k),r=upper_bound(g.begin(),g.end(),g[v[i].sc]+k)-g.begin()-1;
ans+=bt.ask(l,r);
bt.update(v[i].sc,1);
}
while(z<n){
bt.update(v[z].sc,-1);
z++;
}
return ans;
};
int l=0,r=3e9+7;
while(r>l){
int mid=(l+r+1)/2;
if(cal(mid)>m){
r=mid-1;
}
else{
l=mid;
}
}
vector<int> ret;
set<pair<int,int> > s;
int z=0;
for(int i=0;i<n;i++){
while(z<i && v[z].fs+l<v[i].fs){
s.erase({g[v[z].sc],v[z].fs});
z++;
}
for(auto h=s.lower_bound({g[v[i].sc]-l,-3e10});h!=s.end() && ((*h).fs-l<=g[v[i].sc]);h=next(h)){
assert((abs(g[v[i]].sc-(*h).fs))<=l && v[i].fs-(*h).sc<=l);
ret.push_back(max(v[i].fs-(*h).sc,abs(g[v[i].sc]-(*h).fs)));
}
s.insert({g[v[i].sc],v[i].fs});
}
sort(ret.begin(),ret.end());
assert(ret.size()==cal(l));
while(ret.size()<m){
ret.push_back(l+1);
}
for(auto h:ret){
cout << h << '\n';
}
return 0;
}