結果
問題 | 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; }