結果

問題 No.2436 Min Diff Distance
ユーザー sotanishysotanishy
提出日時 2023-08-18 23:43:59
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 311 ms / 2,000 ms
コード長 4,109 bytes
コンパイル時間 3,524 ms
コンパイル使用メモリ 208,640 KB
最終ジャッジ日時 2025-02-16 11:00:55
ジャッジサーバーID
(参考情報)
judge4 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (int i = (int)(s); i < (int)(t); ++i)
#define revrep(i, t, s) for (int i = (int)(t)-1; i >= (int)(s); --i)
#define all(x) begin(x), end(x)
template <typename T>
bool chmax(T& a, const T& b) {
return a < b ? (a = b, 1) : 0;
}
template <typename T>
bool chmin(T& a, const T& b) {
return a > b ? (a = b, 1) : 0;
}
template <typename M>
class SegmentTree {
using T = typename M::T;
public:
SegmentTree() = default;
explicit SegmentTree(int n) : SegmentTree(std::vector<T>(n, M::id())) {}
explicit SegmentTree(const std::vector<T>& v) {
size = 1;
while (size < (int)v.size()) size <<= 1;
node.resize(2 * size, M::id());
std::copy(v.begin(), v.end(), node.begin() + size);
for (int i = size - 1; i > 0; --i)
node[i] = M::op(node[2 * i], node[2 * i + 1]);
}
T operator[](int k) const { return node[k + size]; }
void update(int k, const T& x) {
k += size;
node[k] = x;
while (k >>= 1) node[k] = M::op(node[2 * k], node[2 * k + 1]);
}
T fold(int l, int r) const {
T vl = M::id(), vr = M::id();
for (l += size, r += size; l < r; l >>= 1, r >>= 1) {
if (l & 1) vl = M::op(vl, node[l++]);
if (r & 1) vr = M::op(node[--r], vr);
}
return M::op(vl, vr);
}
template <typename F>
int find_first(int l, F cond) const {
T v = M::id();
for (l += size; l > 0; l >>= 1) {
if (l & 1) {
T nv = M::op(v, node[l]);
if (cond(nv)) {
while (l < size) {
nv = M::op(v, node[2 * l]);
if (cond(nv))
l = 2 * l;
else
v = nv, l = 2 * l + 1;
}
return l + 1 - size;
}
v = nv;
++l;
}
}
return -1;
}
template <typename F>
int find_last(int r, F cond) const {
T v = M::id();
for (r += size; r > 0; r >>= 1) {
if (r & 1) {
--r;
T nv = M::op(node[r], v);
if (cond(nv)) {
while (r < size) {
nv = M::op(node[2 * r + 1], v);
if (cond(nv))
r = 2 * r + 1;
else
v = nv, r = 2 * r;
}
return r - size;
}
v = nv;
}
}
return -1;
}
private:
int size;
std::vector<T> node;
};
struct MaxMonoid {
using T = int;
static T id() { return -1e7; }
static T op(T a, T b) { return max(a, b); }
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
int N;
cin >> N;
vector<tuple<int, int, int>> pts;
int left = 1e9, right = -1e9, top = -1e9, bottom = 1e9;
rep(i, 0, N) {
int x, y;
cin >> x >> y;
--x, --y;
pts.push_back({x, y, i});
chmin(left, x + y);
chmax(right, x + y);
chmin(bottom, x - y);
chmax(top, x - y);
}
auto rotate = [&](const vector<tuple<int, int, int>>& pts) {
vector<tuple<int, int, int>> res;
for (auto [x, y, i] : pts) res.push_back({N - 1 - y, x, i});
return res;
};
vector<int> nearest(N, 1e7);
rep(_, 0, 4) {
SegmentTree<MaxMonoid> st(N);
sort(all(pts));
for (auto [x, y, i] : pts) {
chmin(nearest[i], x + y - st.fold(0, y));
st.update(y, x + y);
}
pts = rotate(pts);
}
int ans = 1e7;
for (auto [x, y, i] : pts) {
int xx = x + y, yy = x - y;
int farthest = max({xx - left, right - xx, yy - bottom, top - yy});
chmin(ans, farthest - nearest[i]);
}
cout << ans << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0