結果

問題 No.2897 ２集合間距離
ユーザー 👑 hos.lyrichos.lyric
提出日時 2024-09-20 22:24:36
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 352 ms / 3,500 ms
コード長 2,781 bytes
コンパイル時間 1,246 ms
コンパイル使用メモリ 118,208 KB
実行使用メモリ 9,672 KB
最終ジャッジ日時 2024-09-20 22:24:41
合計ジャッジ時間 5,164 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 3 ms
6,940 KB
testcase_14 AC 10 ms
6,944 KB
testcase_15 AC 16 ms
6,944 KB
testcase_16 AC 327 ms
9,600 KB
testcase_17 AC 326 ms
9,640 KB
testcase_18 AC 325 ms
9,596 KB
testcase_19 AC 327 ms
9,672 KB
testcase_20 AC 352 ms
9,628 KB
testcase_21 AC 319 ms
9,644 KB
testcase_22 AC 316 ms
9,600 KB
testcase_23 AC 321 ms
9,612 KB
権限があれば一括ダウンロードができます

ソースコード

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")


constexpr int INF = 1001001001;
void bChmax(vector<int> &bit, int pos, int val) {
  const int bitN = bit.size();
  for (int x = pos; x < bitN; x |= x + 1) chmax(bit[x], val);
}
int bMax(const vector<int> &bit, int pos) {
  int ret = -INF;
  for (int x = pos; x > 0; x &= x - 1) chmax(ret, bit[x - 1]);
  return ret;
}


constexpr int LIM = 1000;

int N[2];
vector<int> X[2], Y[2];

int main() {
  for (; ; ) {
    for (int h = 0; h < 2; ++h) {
      if (!~scanf("%d", &N[h])) return 0;
      X[h].resize(N[h]);
      Y[h].resize(N[h]);
      for (int u = 0; u < N[h]; ++u) {
        scanf("%d%d", &X[h][u], &Y[h][u]);
      }
    }
    
    int ans = INF;
    for (int dir = 0; dir < 4; ++dir) {
      vector<pair<int, int>> es(N[0] + N[1]);
      for (int u = 0; u < N[0]; ++u) es[u] = make_pair(X[0][u], u);
      for (int v = 0; v < N[1]; ++v) es[N[0] + v] = make_pair(X[1][v], N[0] + v);
      sort(es.begin(), es.end());
      vector<int> bit(LIM + 1, -INF);
      for (const auto &e : es) {
        if (e.second < N[0]) {
          const int u = e.second;
          bChmax(bit, Y[0][u], X[0][u] + Y[0][u]);
        } else {
          const int v = e.second - N[0];
          const int res = bMax(bit, Y[1][v] + 1);
          chmin(ans, (X[1][v] + Y[1][v]) - res);
        }
      }
      for (int h = 0; h < 2; ++h) {
        for (int u = 0; u < N[h]; ++u) {
          const int x = X[h][u];
          const int y = Y[h][u];
          X[h][u] = LIM - y;
          Y[h][u] = x;
        }
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}
0