結果
問題 | No.2436 Min Diff Distance |
ユーザー |
|
提出日時 | 2023-08-18 22:20:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 725 ms / 2,000 ms |
コード長 | 1,824 bytes |
コンパイル時間 | 1,206 ms |
コンパイル使用メモリ | 98,692 KB |
実行使用メモリ | 43,008 KB |
最終ジャッジ日時 | 2024-11-28 08:02:22 |
合計ジャッジ時間 | 10,867 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#include<iostream>#include<algorithm>#include<vector>#include<queue>#include<cassert>#include<map>//#include<atcoder/modint>using namespace std;//using mint=atcoder::modint998244353;#include<vector>#include<algorithm>template<typename T>struct rangefreq{int n;vector<vector<T> >dat;rangefreq(const vector<T>&v={}){n=1;while(n<v.size())n<<=1;dat.assign(2*n-1,{});for(int i=0;i<v.size();i++)dat[i+n-1].push_back(v[i]);for(int i=n-2;i>=0;i--){dat[i].resize(dat[i*2+1].size()+dat[i*2+2].size());merge(dat[i*2+1].begin(),dat[i*2+1].end(),dat[i*2+2].begin(),dat[i*2+2].end(),dat[i].begin());}}int query(int a,int b,T x,int k=0,int l=0,int r=-1)const//[a,b) count(*<x){if(r<0)r=n;if(b<=l||r<=a)return 0;else if(a<=l&&r<=b)return lower_bound(dat[k].begin(),dat[k].end(),x)-dat[k].begin();else return query(a,b,x,k*2+1,l,(l+r)/2)+query(a,b,x,k*2+2,(l+r)/2,r);}};int N;int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>N;vector<pair<int,int> >P(N);int lx=1e9,rx=-1e9,ly=1e9,ry=-1e9;for(int i=0;i<N;i++){int x,y;cin>>x>>y;P[i]=make_pair(x+y-2,x-y);lx=min(lx,P[i].first);rx=max(rx,P[i].first);ly=min(ly,P[i].second);ry=max(ry,P[i].second);}sort(P.begin(),P.end());vector<int>X(N),Y(N);for(int i=0;i<N;i++)X[i]=P[i].first,Y[i]=P[i].second;rangefreq<int>seg(Y);int check=2*N;for(int i=0;i<N;i++){int x=P[i].first,y=P[i].second;int mx=max({rx-x,x-lx,ry-y,y-ly});check=min(check,mx);while(check>0){int mn=mx-check;int lx=x-mn,rx=x+mn;int ly=y-mn,ry=y+mn;int li=lower_bound(X.begin(),X.end(),lx)-X.begin();int ri=upper_bound(X.begin(),X.end(),rx)-X.begin();if(seg.query(li,ri,ry+1)-seg.query(li,ri,ly)>=2)break;check--;}}cout<<check<<endl;}