結果
問題 | No.2436 Min Diff Distance |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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;elsev = 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;elsev = 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;}