| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 945795 | beepbeepsheep | Road Construction (JOI21_road_construction) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define iii tuple<ll,ll,ll>
#ifndef DEBUG
#define cerr if (0) cerr
#define endl '\n'
#endif // DEBUG
const ll maxn=2e5+5e4+5;
const ll inf=1e15;
const ll mod=1e9+7;
ll n;
ll x[maxn],y[maxn];
ii ranges[maxn];
vector<ll> pos;
vector<ii> updates;
ll fen[maxn];
void upd(ll x, ll v){
while (x<maxn){
fen[x]+=v;
x+=(x&-x);
}
}
ll query(ll x){
ll ans=0;
while (x){
ans+=fen[x];
x-=(x&-x);
}
return ans;
}
ll query(ll x, ll y){
return query(y)-query(x-1);
}
ll check(ll len){
vector<tuple<ll,ll,ll>> queries;
for (int i=1;i<=n;i++){
queries.emplace_back(y[i]-len-1,i,-1);
//exclusive
queries.emplace_back(y[i]+len,i,1);
//inclusive
ranges[i].first=lower_bound(pos.begin(),pos.end(),x[i]-len)
-pos.begin();
ranges[i].second=upper_bound(pos.begin(),pos.end(),x[i]+len)
-pos.begin()-1;
}
sort(queries.begin(),queries.end());
ll ans=0,ptr=0;
memset(fen,0,sizeof(fen));
for (auto [a,b,c]:queries){
while (ptr!=updates.size() &&
updates[ptr].first<=a){
upd(updates[ptr].second,1);
ptr++;
}
ans+=c*(query(ranges[b].first,ranges[b].second));
}
return (ans-n)/2;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
ll a,b,k;
cin>>n>>k;
assert(k==1);
for (int i=1;i<=n;i++){
cin>>a> >b;
x[i]=a+b,y[i]=a-b;
pos.emplace_back(x[i]);
}
pos.emplace_back(-inf);
sort(pos.begin(),pos.end());
pos.erase(unique(pos.begin(),pos.end()),pos.end());
for (int i=1;i<=n;i++){
ll res=lower_bound(pos.begin(),pos.end(),x[i])-pos.begin();
updates.emplace_back(y[i],res);
}
sort(updates.begin(),updates.end());
ll l=1,r=4'000'000'005,m;
while (l!=r-1){
m=(l+r)>>1;
if (check(m)) r=m;
else l=m;
}
cout<<r;
return 0;
}