Submission #697176

#	Time	Username	Problem	Language	Result	Execution time	Memory
697176		peijar	Road Construction (JOI21_road_construction)	C++17	100 / 100	6736 ms	19288 KiB

road_construction

#include <bits/stdc++.h>
#define int long long
using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

template <class T> class Fenwick {
public:
  int lim;
  vector<T> bit;

  Fenwick(int n) : lim(n + 1), bit(lim) {}

  void upd(int pos, T val) {
    for (pos++; pos < lim; pos += pos & -pos)
      bit[pos] += val;
  }

  T sum(int r) { // < r
    T ret = 0;
    for (; r; r -= r & -r)
      ret += bit[r];
    return ret;
  }

  T sum(int l, int r) { // [l, r)
    return sum(r) - sum(l);
  }
};

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int N, K;
  cin >> N >> K;
  K *= 2;
  vector<pair<int, int>> points(N);
  for (auto &[x, y] : points) {
    cin >> x >> y;
    tie(x, y) = make_pair(x - y, x + y);
  }

  vector<int> valY;
  for (auto [x, y] : points)
    valY.push_back(y);

  sort(valY.begin(), valY.end());
  valY.resize(unique(valY.begin(), valY.end()) - valY.begin());
  int nbY = valY.size();

  auto getId = [&](int y) {
    return lower_bound(valY.begin(), valY.end(), y) - valY.begin();
  };
  sort(points.begin(), points.end());

  auto countSmaller = [&](int L) { // cb avec dis <= L?
    int sol = 0;
    Fenwick<int> fen(nbY);

    int l = 0, r = 0;
    for (auto [x, y] : points) {
      while (r < N and points[r].first <= x + L)
        fen.upd(getId(points[r++].second), 1);
      while (l < r and points[l].first < x - L) {
        fen.upd(getId(points[l++].second), -1);
      }
      assert(l < r);

      int fstGood = lower_bound(valY.begin(), valY.end(), y - L) - valY.begin();
      int fstBad = upper_bound(valY.begin(), valY.end(), y + L) - valY.begin();
      sol += fen.sum(fstGood, fstBad) - 1;
    }
    return sol;
  };

  int lo = 0, up = 1e18;
  while (lo < up) {
    int mid = (lo + up + 1) / 2;

    if (countSmaller(mid) <= K)
      lo = mid;
    else
      up = mid - 1;
  }

  int L = lo;
  vector<int> costs;
  int add = K - countSmaller(L);
  for (int i = 0; i < add; ++i)
    costs.push_back(L + 1);

  int l = 0, r = 0;
  set<pair<int, int>> possible;
  for (int i = 0; i < N; ++i) {
    auto [x, y] = points[i];
    while (r < N and points[r].first <= x + L) {
      possible.emplace(points[r].second, r);
      ++r;
    }
    while (l < r and points[l].first < x - L) {
      possible.erase({points[l].second, l});
      ++l;
    }
    for (auto it = possible.lower_bound(pair(y - L, 0));
         it != possible.end() and it->first <= y + L; ++it) {
      auto [x2, y2] = points[it->second];
      if (i != it->second)
        costs.push_back(max(abs(x2 - x), abs(y2 - y)));
    }
  }
  sort(costs.begin(), costs.end());
  for (int i = 0; i < K; i += 2)
    cout << costs[i] << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35