結果
問題 | No.2436 Min Diff Distance |
ユーザー |
![]() |
提出日時 | 2023-08-18 23:23:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 566 ms / 2,000 ms |
コード長 | 1,741 bytes |
コンパイル時間 | 4,850 ms |
コンパイル使用メモリ | 261,380 KB |
最終ジャッジ日時 | 2025-02-16 10:50:20 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 4000000000000000001 using P = pair<long long,long long>; P op(P a,P b){ return make_pair(min(a.first,b.first),max(a.second,b.second)); } P e(){ return make_pair(Inf64,-Inf64); } int main(){ int n; cin>>n; vector<pair<long long,long long>> p(n); rep(i,n){ cin>>p[i].first>>p[i].second; } sort(p.begin(),p.end()); long long ans = Inf64; vector<long long> Ms(n,-Inf64),ms(n,Inf64); { segtree<P,op,e> seg0(n+5),seg1(n+5); rep(i,n){ long long x = p[i].first; long long y = p[i].second; long long m = x,M = x; m += min(y + seg0.prod(0,y).first, seg1.prod(y,n+5).first - y); M += max(y + seg0.prod(0,y).second, seg1.prod(y,n+5).second - y); Ms[i] = max(Ms[i],M); ms[i] = min(ms[i],m); //cout<<x<<','<<y<<' '<<m<<' '<<M<<endl; //ans = min(ans,M-m); seg0.set(y,op(seg0.get(y), make_pair(-x-y,-x-y))); seg1.set(y,op(seg1.get(y), make_pair(-x+y,-x+y))); } } { segtree<P,op,e> seg0(n+5),seg1(n+5); for(int i=n-1;i>=0;i--){ long long x = p[i].first; long long y = p[i].second; long long m = -x,M = -x; m += min(y + seg0.prod(0,y).first, seg1.prod(y,n+5).first - y); M += max(y + seg0.prod(0,y).second, seg1.prod(y,n+5).second - y); Ms[i] = max(Ms[i],M); ms[i] = min(ms[i],m); //cout<<x<<','<<y<<' '<<m<<' '<<M<<endl; //ans = min(ans,M-m); seg0.set(y,op(seg0.get(y), make_pair(x-y,x-y))); seg1.set(y,op(seg1.get(y), make_pair(x+y,x+y))); } } rep(i,n)ans = min(ans,Ms[i]-ms[i]); cout<<ans<<endl; return 0; }