Submission #387556

#	Time	Username	Problem	Language	Result	Execution time	Memory
387556		rama_pang	Road Construction (JOI21_road_construction)	C++17	5 / 100	10092 ms	81204 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 = 1e7;

  int node_cnt = 1;
  Node node[MAX_SIZE];

  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];
  }

  const auto Count = [&](int i, lint dist) {
    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;
    return Persistent::Query(tree[xhi], 0, int(coordY.size()) - 1, ylo, yhi) -
           Persistent::Query(tree[xlo - 1], 0, int(coordY.size()) - 1, ylo, yhi);
  };

  vector<lint> ans;
  priority_queue<array<lint, 3>, vector<array<lint, 3>>, greater<array<lint, 3>>> pq; // (dist, #copy, source)

  vector<lint> dist(N);

  const auto Relax = [&](int i) {
    lint count_old = Count(i, dist[i]);
    lint lo = dist[i] + 1, hi = 1e10;
    while (lo < hi) {
      lint md = (lo + hi) / 2;
      if (Count(i, md) - count_old > 0) {
        hi = md;
      } else {
        lo = md + 1;
      }
    }
    dist[i] = lo;
    pq.push({lo, Count(i, lo) - count_old, i});
  };

  for (int i = 0; i < N; i++) {
    Relax(i);
  }

  while (ans.size() < 2 * K) {
    auto top = pq.top(); pq.pop();
    ans.emplace_back(top[0]); top[1]--;
    if (top[1] > 0) {
      pq.emplace(top);
    } else {
      Relax(top[2]);
    }
  }

  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:128:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  128 |   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:138:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  138 |   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