結果
問題 | No.2436 Min Diff Distance |
ユーザー |
![]() |
提出日時 | 2023-08-13 08:50:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 336 ms / 2,000 ms |
コード長 | 1,859 bytes |
コンパイル時間 | 1,991 ms |
コンパイル使用メモリ | 209,360 KB |
最終ジャッジ日時 | 2025-02-16 07:41:17 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/segtree> using namespace std; using ll = long long; template <typename T, typename U> inline bool chmin(T &x, U y) { return (y < x) ? (x = y, true) : false; } template <typename T, typename U> inline bool chmax(T &x, U y) { return (x < y) ? (x = y, true) : false; } const ll linf = 1e15; ll op(ll a, ll b){ return min(a,b); } ll e(){ return linf; } vector<ll> min_dist(int n, vector<ll> xs, vector<ll> ys){ vector<vector<pair<ll,int>>> xys(n); for (int i = 0; i < n; i++){ xys[xs[i]].emplace_back(ys[i],i); } atcoder::segtree<ll,op,e> lseg(n), rseg(n); vector<ll> ans(n,linf); for (ll x = 0; x < n; x++){ sort(xys[x].begin(),xys[x].end()); for (auto [y, i] : xys[x]){ ll le = lseg.prod(0,y) + x + y; ll ri = rseg.prod(y,n) + x - y; chmin(ans[i],min(le,ri)); lseg.set(y,-x-y); rseg.set(y,-x+y); } } return ans; } int main(){ int n; cin >> n; ll pma = -linf, pmi = linf, mma = -linf, mmi = linf; vector<ll> xs(n), ys(n); for (int i = 0; i < n; i++){ cin >> xs[i] >> ys[i]; xs[i]--, ys[i]--; chmax(pma,xs[i]+ys[i]); chmin(pmi,xs[i]+ys[i]); chmax(mma,xs[i]-ys[i]); chmin(mmi,xs[i]-ys[i]); } vector<ll> mas(n,-linf), mis(n,linf); vector<ll> ul = min_dist(n,xs,ys); for (int i = 0; i < n; i++){ ll p = xs[i]+ys[i]; ll m = xs[i]-ys[i]; chmax(mas[i],max(pma-p,p-pmi)); chmax(mas[i],max(mma-m,m-mmi)); chmin(mis[i],ul[i]); xs[i] = n-1-xs[i]; ys[i] = n-1-ys[i]; } vector<ll> dr = min_dist(n,xs,ys); ll ans = linf; for (int i = 0; i < n; i++){ chmin(mis[i],dr[i]); chmin(ans,mas[i]-mis[i]); } cout << ans << endl; }