結果

問題 No.2436 Min Diff Distance
コンテスト
ユーザー hos.lyric
提出日時 2023-12-17 20:06:41
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,522 bytes
コンパイル時間 1,912 ms
コンパイル使用メモリ 128,316 KB
実行使用メモリ 29,896 KB
最終ジャッジ日時 2024-09-27 08:03:56
合計ジャッジ時間 6,405 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


template <class X, class Y, class T> struct StaticPointAddRectSum {
  struct Rect {
    X x0, x1;
    Y y0, y1;
  };
  vector<pair<X, Y>> as;
  vector<Rect> bs;
  vector<T> vals, anss;
  // Adds val to (x, y).
  void add(X x, Y y, const T &val) {
    as.emplace_back(x, y);
    vals.push_back(val);
  }
  // Gets sum of [x0, x1) * [y0, y1).
  //   ~~> Gets (x*, y*)
  void get(X x0, X x1, Y y0, Y y1) {
    assert(x0 <= x1); assert(y0 <= y1);
    bs.push_back(Rect{x0, x1, y0, y1});
  }

  void run() {
    const int asLen = as.size(), bsLen = bs.size();

    // same x ==> get then add
    vector<pair<X, int>> events((bsLen << 1) + asLen);
    for (int i = 0; i < asLen; ++i) {
      events[(bsLen << 1) + i] = std::make_pair(as[i].first, (bsLen << 1) + i);
    }
    for (int j = 0; j < bsLen; ++j) {
      events[j << 1    ] = std::make_pair(bs[j].x0, j << 1    );
      events[j << 1 | 1] = std::make_pair(bs[j].x1, j << 1 | 1);
    }
    std::sort(events.begin(), events.end());

    vector<Y> ys(asLen);
    for (int i = 0; i < asLen; ++i) {
      ys[i] = as[i].second;
    }
    std::sort(ys.begin(), ys.end());
    ys.erase(std::unique(ys.begin(), ys.end()), ys.end());
    const int ysLen = ys.size();
    vector<T> bit(ysLen, 0);

    anss.assign(bsLen, 0);
    for (const auto &event : events) {
      if (event.second >= bsLen << 1) {
        const int i = event.second - (bsLen << 1);
        for (int l = std::lower_bound(ys.begin(), ys.end(), as[i].second) - ys.begin(); l < ysLen; l |= l + 1) {
          bit[l] += vals[i];
        }
      } else {
        const int j = event.second >> 1;
        T sum = 0;
        for (int l = std::lower_bound(ys.begin(), ys.end(), bs[j].y0) - ys.begin(); l > 0; l &= l - 1) {
          sum -= bit[l - 1];
        }
        for (int l = std::lower_bound(ys.begin(), ys.end(), bs[j].y1) - ys.begin(); l > 0; l &= l - 1) {
          sum += bit[l - 1];
        }
        (event.second & 1) ? (anss[j] += sum) : (anss[j] -= sum);
      }
    }
  }
};

////////////////////////////////////////////////////////////////////////////////


int N;
vector<int> X, Y;

int minA, maxA, minB, maxB;
vector<int> A, B;

bool check(Int thr) {
  StaticPointAddRectSum<int, int, int> f;
  for (int i = 0; i < N; ++i) {
    const Int mx = max({A[i] - minA, maxA - A[i], B[i] - minB, maxB - B[i]});
    if (mx <= thr) {
      return true;
    }
    f.add(A[i], B[i], 1);
    f.get(A[i] - (mx - thr) + 1, A[i] + (mx - thr), B[i] - (mx - thr) + 1, B[i] + (mx - thr));
  }
  f.run();
  for (int i = 0; i < N; ++i) {
    if (f.anss[i] <= 1) {
      return true;
    }
  }
  return false;
}

int main() {
  for (; ~scanf("%d", &N); ) {
    X.resize(N);
    Y.resize(N);
    for (int i = 0; i < N; ++i) {
      scanf("%d%d", &X[i], &Y[i]);
    }
    
    A.resize(N);
    B.resize(N);
    for (int i = 0; i < N; ++i) {
      A[i] = X[i] + Y[i];
      B[i] = X[i] - Y[i];
    }
    minA = *min_element(A.begin(), A.end());
    maxA = *max_element(A.begin(), A.end());
    minB = *min_element(B.begin(), B.end());
    maxB = *max_element(B.begin(), B.end());
    
    int lo = -1, hi = max(maxA - minA, maxB - minB);
    for (; lo + 1 < hi; ) {
      const Int mid = (lo + hi) / 2;
      (check(mid) ? hi : lo) = mid;
    }
    printf("%d\n", hi);
  }
  return 0;
}
0