結果
| 問題 |
No.2436 Min Diff Distance
|
| コンテスト | |
| ユーザー |
 siro53
|
| 提出日時 | 2023-08-18 23:51:30 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,364 bytes |
| コンパイル時間 | 13,641 ms |
| コンパイル使用メモリ | 314,540 KB |
| 最終ジャッジ日時 | 2025-02-16 11:03:23 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 3 TLE * 1 -- * 19 |
ソースコード
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma region Macros
#include <bits/stdc++.h>
using namespace std;
template <class T> inline bool chmax(T &a, T b) {
if(a < b) {
a = b;
return 1;
}
return 0;
}
template <class T> inline bool chmin(T &a, T b) {
if(a > b) {
a = b;
return 1;
}
return 0;
}
#ifdef DEBUG
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
os << '(' << p.first << ',' << p.second << ')';
return os;
}
template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
os << '{';
for(int i = 0; i < (int)v.size(); i++) {
if(i) { os << ','; }
os << v[i];
}
os << '}';
return os;
}
void debugg() { cerr << endl; }
template <class T, class... Args>
void debugg(const T &x, const Args &... args) {
cerr << " " << x;
debugg(args...);
}
#define debug(...) \
cerr << __LINE__ << " [" << #__VA_ARGS__ << "]: ", debugg(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif
struct Setup {
Setup() {
cin.tie(0);
ios::sync_with_stdio(false);
cout << fixed << setprecision(15);
}
} __Setup;
using ll = long long;
#define OVERLOAD3(_1, _2, _3, name, ...) name
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define REP1(i, n) for(int i = 0; i < int(n); i++)
#define REP2(i, a, b) for(int i = (a); i < int(b); i++)
#define REP(...) OVERLOAD3(__VA_ARGS__, REP2, REP1)(__VA_ARGS__)
#define UNIQUE(v) sort(ALL(v)), (v).erase(unique(ALL(v)), (v).end())
#define REVERSE(v) reverse(ALL(v))
#define SZ(v) ((int)(v).size())
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
constexpr int MOD = 1000000007;
constexpr int MOD2 = 998244353;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
void Case(int i) { cout << "Case #" << i << ": "; }
int popcount(int x) { return __builtin_popcount(x); }
ll popcount(ll x) { return __builtin_popcountll(x); }
#pragma endregion Macros
#line 2 "data-structure-2d/fenwick-tree-on-range-tree.hpp"
// S ... size_type
// T ... value_type
template <typename S, typename T>
struct FenwickRangeTree {
struct BIT {
int N;
vector<T> data;
BIT() = default;
BIT(int size) { init(size); }
void init(int size) {
N = size;
data.assign(N + 1, 0);
}
void add(int k, T x) {
for (++k; k <= N; k += k & -k) data[k] += x;
}
T sum(int k) const {
T ret = T();
for (; k; k -= k & -k) ret += data[k];
return ret;
}
inline T sum(int l, int r) const {
T ret = T();
while (l != r) {
if (l < r) {
ret += data[r];
r -= r & -r;
} else {
ret -= data[l];
l -= l & -l;
}
}
return ret;
}
};
using P = pair<S, S>;
S N, M;
vector<BIT> bit;
vector<vector<S>> ys;
vector<P> ps;
FenwickRangeTree() = default;
void add_point(S x, S y) { ps.push_back(make_pair(x, y)); }
void build() {
sort(begin(ps), end(ps));
ps.erase(unique(begin(ps), end(ps)), end(ps));
N = ps.size();
bit.resize(N + 1);
ys.resize(N + 1);
for (int i = 0; i <= N; ++i) {
for (int j = i + 1; j <= N; j += j & -j) ys[j].push_back(ps[i].second);
sort(begin(ys[i]), end(ys[i]));
ys[i].erase(unique(begin(ys[i]), end(ys[i])), end(ys[i]));
bit[i].init(ys[i].size());
}
}
int id(S x) const {
return lower_bound(
begin(ps), end(ps), make_pair(x, S()),
[](const P& a, const P& b) { return a.first < b.first; }) -
begin(ps);
}
int id(int i, S y) const {
return lower_bound(begin(ys[i]), end(ys[i]), y) - begin(ys[i]);
}
void add(S x, S y, T a) {
int i = lower_bound(begin(ps), end(ps), make_pair(x, y)) - begin(ps);
assert(ps[i] == make_pair(x, y));
for (++i; i <= N; i += i & -i) bit[i].add(id(i, y), a);
}
T sum(S x, S y) const {
T ret = T();
for (int a = id(x); a; a -= a & -a) ret += bit[a].sum(id(a, y));
return ret;
}
T sum(S xl, S yl, S xr, S yr) const {
T ret = T();
int a = id(xl), b = id(xr);
while (a != b) {
if (a < b) {
ret += bit[b].sum(id(b, yl), id(b, yr));
b -= b & -b;
} else {
ret -= bit[a].sum(id(a, yl), id(a, yr));
a -= a & -a;
}
}
return ret;
}
};
/*
* @brief 領域木(Binary Indexed Tree)
*/
void solve() {
int N;
cin >> N;
vector<int> x(N), y(N);
REP(i, N) cin >> x[i] >> y[i];
vector<int> mxs(N, -INF), mns(N, -INF);
// max
{
vector<int> ord(N);
iota(ALL(ord), 0);
sort(ALL(ord), [&](int i, int j) { return (x[i] + y[i] < x[j] + y[j]); });
REP(i, N) {
int L = ord[0], R = ord[N-1];
int idx = ord[i];
chmax(mxs[idx], abs((x[idx] + y[idx]) - (x[L] + y[L])));
chmax(mxs[idx], abs((x[idx] + y[idx]) - (x[R] + y[R])));
}
iota(ALL(ord), 0);
sort(ALL(ord), [&](int i, int j) { return (x[i] - y[i] < x[j] - y[j]); });
REP(i, N) {
int L = ord[0], R = ord[N-1];
int idx = ord[i];
chmax(mxs[idx], abs((x[idx] - y[idx]) - (x[L] - y[L])));
chmax(mxs[idx], abs((x[idx] - y[idx]) - (x[R] - y[R])));
}
}
debug(mxs);
// min
{
FenwickRangeTree<int, int> bt;
REP(i, N) bt.add_point(x[i] + y[i], x[i] - y[i]);
bt.build();
REP(i, N) bt.add(x[i] + y[i], x[i] - y[i], 1);
REP(i, N) {
int U = x[i] + y[i], V = x[i] - y[i];
auto check = [&](int d) -> bool {
int s = bt.sum(U - d, V - d, U + d + 1, V + d + 1);
return s > 1;
};
int ok = N + 1, ng = 0;
while(ok - ng > 1) {
int mid = (ok + ng) / 2;
(check(mid) ? ok : ng) = mid;
}
mns[i] = ok;
}
}
debug(mns);
int ans = INF;
REP(i, N) chmin(ans, mxs[i] - mns[i]);
cout << ans << endl;
}
int main() {
int T = 1;
// cin >> T;
while(T--) solve();
}