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