Submission #387550

#	Time	Username	Problem	Language	Result	Execution time	Memory
387550		rama_pang	Road Construction (JOI21_road_construction)	C++17	5 / 100	10114 ms	2097156 KiB

road_construction

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

using lint = long long;
const lint inf = 1e18;

namespace Persistent {
  struct Node {
    int sum = 0;
    int lc = 0;
    int rc = 0;
  };

  const int MAX_SIZE = 2e7;

  int node_cnt = 1;
  array<Node, MAX_SIZE> node;

  int NewNode() {
    return node_cnt++;
  }

  int CopyNode(int n) {
    node[node_cnt] = node[n];
    return node_cnt++;
  }

  int Build(int tl, int tr) {
    int n = NewNode();
    if (tl == tr) return n;
    int md = (tl + tr) / 2;
    node[n].lc = Build(tl, md);
    node[n].rc = Build(md + 1, tr);
    return n;
  }

  int Update(int n, int tl, int tr, int p, int x) {
    n = CopyNode(n);
    if (tl == tr) {
      node[n].sum += x;
      return n;
    }
    int md = (tl + tr) / 2;
    node[n].sum += x;
    if (p <= md) {
      node[n].lc = Update(node[n].lc, tl, md, p, x);
    } else {
      node[n].rc = Update(node[n].rc, md + 1, tr, p, x);
    }
    return n;
  }

  int Query(int n, int tl, int tr, int l, int r) {
    if (tl > r || l > tr || tl > tr || l > r) return 0;
    if (l <= tl && tr <= r) return node[n].sum;
    int md = (tl + tr) / 2;
    return Query(node[n].lc, tl, md, l, r) + Query(node[n].rc, md + 1, tr, l, r);
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N, K;
  cin >> N >> K;
  vector<lint> X(N), Y(N);
  vector<lint> coordX = {-inf, inf}, coordY = {-inf, inf};
  for (int i = 0; i < N; i++) {
    cin >> X[i] >> Y[i];
    tie(X[i], Y[i]) = pair(X[i] + Y[i], X[i] - Y[i]);
    coordX.emplace_back(X[i]);
    coordY.emplace_back(Y[i]);
  }

  sort(begin(coordX), end(coordX));
  sort(begin(coordY), end(coordY));
  coordX.resize(unique(begin(coordX), end(coordX)) - begin(coordX));
  coordY.resize(unique(begin(coordY), end(coordY)) - begin(coordY));

  vector<int> ord(N);
  iota(begin(ord), end(ord), 0);
  sort(begin(ord), end(ord), [&](int i, int j) { return X[i] < X[j]; });

  vector<int> tree(coordX.size());
  int prv = tree[0] = Persistent::Build(0, int(coordY.size()) - 1);

  for (auto i : ord) {
    int xid = lower_bound(begin(coordX), end(coordX), X[i]) - begin(coordX);
    int yid = lower_bound(begin(coordY), end(coordY), Y[i]) - begin(coordY);
    tree[xid] = Persistent::Update(prv, 0, int(coordY.size()) - 1, yid, 1);
    prv = tree[xid];
  }

  // for (int i = 0; i < N; i++) {
  //   cout << X[i] << ' ' << Y[i] << '\n';
  // }
  // for (int i = 0; i < coordX.size(); i++) {
  //   for (int j = 0; j < coordY.size(); j++) {
  //     cout << Persistent::Query(tree[i], 0, int(coordY.size()) - 1, j, j) << ' ';
  //   }
  //   cout << '\n';
  // }

  const auto Count = [&](lint dist) -> int {
    lint res = 0;
    for (int i = 0; i < N; i++) {
      int xlo = lower_bound(begin(coordX), end(coordX), X[i] - dist) - begin(coordX);
      int xhi = upper_bound(begin(coordX), end(coordX), X[i] + dist) - begin(coordX) - 1;
      int ylo = lower_bound(begin(coordY), end(coordY), Y[i] - dist) - begin(coordY);
      int yhi = upper_bound(begin(coordY), end(coordY), Y[i] + dist) - begin(coordY) - 1;
      res += Persistent::Query(tree[xhi], 0, int(coordY.size()) - 1, ylo, yhi);
      res -= Persistent::Query(tree[xlo - 1], 0, int(coordY.size()) - 1, ylo, yhi);
    }
    return res - N;
  };

  const auto Generate = [&](lint dist) -> vector<lint> {
    int sz = coordX.size();
    vector<vector<pair<lint, int>>> tree(2 * sz); // (Y, index)
    for (int i = 0; i < N; i++) {
      int xid = lower_bound(begin(coordX), end(coordX), X[i]) - begin(coordX);
      tree[sz + xid].emplace_back(Y[i], i);
    }
    for (int i = sz; i < sz + sz; i++) {
      sort(begin(tree[i]), end(tree[i]));
    }
    for (int i = sz - 1; i > 0; i--) {
      merge(begin(tree[i * 2]), end(tree[i * 2]), begin(tree[i * 2 + 1]), end(tree[i * 2 + 1]), back_inserter(tree[i]));
    }

    vector<pair<int, int>> pairs;
    for (int i = 0; i < N; i++) {
      int xlo = lower_bound(begin(coordX), end(coordX), X[i] - dist) - begin(coordX);
      int xhi = upper_bound(begin(coordX), end(coordX), X[i] + dist) - begin(coordX) - 1;
      for (xlo += sz, xhi += sz + 1; xlo < xhi; xlo /= 2, xhi /= 2) {
        if (xlo & 1) {
          auto it = lower_bound(begin(tree[xlo]), end(tree[xlo]), pair(Y[i] - dist, -1));
          while (it != end(tree[xlo]) && it->first <= Y[i] + dist) {
            pairs.emplace_back(i, it->second);
            it++;
          }
          xlo++;
        }
        if (xhi & 1) {
          xhi--;
          auto it = lower_bound(begin(tree[xhi]), end(tree[xhi]), pair(Y[i] - dist, -1));
          while (it != end(tree[xhi]) && it->first <= Y[i] + dist) {
            pairs.emplace_back(i, it->second);
            it++;
          }
        }
      }
    }

    vector<lint> res;
    for (auto [i, j] : pairs) {
      if (i != j) {
        res.emplace_back(max(abs(X[i] - X[j]), abs(Y[i] - Y[j])));
      }
    }
    return res;
  };

  lint lo = 0, hi = 1e10;
  while (lo < hi) {
    lint md = (lo + hi) / 2;
    if (Count(md) >= 2 * K) {
      hi = md;
    } else {
      lo = md + 1;
    }
  }

  vector<lint> ans = Generate(lo - 1);
  while (ans.size() < 2 * K) {
    ans.emplace_back(lo);
  }

  sort(begin(ans), end(ans));
  assert(ans.size() == 2 * K);
  for (int i = 0; i < K; i++) {
    assert(ans[i * 2] == ans[i * 2 + 1]);
    cout << ans[i * 2] << '\n';
  }
  return 0;
}

Compilation message (stderr)

road_construction.cpp: In function 'int main()':
road_construction.cpp:176:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  176 |   while (ans.size() < 2 * K) {
      |          ~~~~~~~~~~~^~~~~~~
In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from road_construction.cpp:1:
road_construction.cpp:181:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  181 |   assert(ans.size() == 2 * K);
      |          ~~~~~~~~~~~^~~~~~~~

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