Submission #1127357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127357		sleepntsheep	Road Construction (JOI21_road_construction)	C++17	100 / 100	3312 ms	922164 KiB

road_construction

/*model code from joi website */
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

using usize = std::size_t;
using i64 = std::int64_t;

using pair = std::pair<i64, usize>;

static constexpr usize digits = 19;
static constexpr i64 INF = 1e10;

struct p_segtree {
  p_segtree *left, *right;
  pair min;

  p_segtree() : left(), right(), min(INF, 0) {}
  p_segtree(pair min_) : left(), right(), min(min_) {}
  p_segtree(p_segtree *l, p_segtree *r)
      : left(l), right(r), min(std::min(l->min, r->min)) {}

  static p_segtree init(usize d = digits) {
    if (d == 0) {
      return {};
    }
    d -= 1;
    auto c = new p_segtree(init(d));
    return {c, c};
  }

  pair get_min(usize l, usize r, usize ll = 0, usize rr = 1 << digits) {
    if (r <= ll || rr <= l) {
      return {INF, 0};
    }
    if (l <= ll && rr <= r) {
      return min;
    }
    usize m = (ll + rr) / 2;
    return std::min(left->get_min(l, r, ll, m), right->get_min(l, r, m, rr));
  }

  p_segtree update(usize i, i64 v, usize d = digits) {
    if (d == 0) {
      return {{v, i}};
    }
    d -= 1;
    if (i >> d & 1) {
      return {left, new p_segtree(right->update(i, v, d))};
    } else {
      return {new p_segtree(left->update(i, v, d)), right};
    }
  }
};

struct compress {
  std::vector<pair> v;
  void add(pair x) { v.push_back(x); }
  void build() { std::sort(v.begin(), v.end()); }
  usize get(pair x) {
    return std::lower_bound(v.begin(), v.end(), x) - v.begin();
  }
};

struct town {
  i64 X, Y;
};

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  usize N, K;
  std::cin >> N >> K;
  std::vector<town> towns(N);
  for (auto &[X, Y] : towns) {
    std::cin >> X >> Y;
  }

  std::sort(towns.begin(), towns.end(),
            [&](const auto &l, const auto &r) { return l.X < r.X; });
  compress yc;
  for (usize i = 0; i != N; i += 1) {
    const auto &[X, Y] = towns[i];
    yc.add({Y, i});
  }
  yc.build();

  std::vector<p_segtree> u(N + 1), d(N + 1);
  u[0] = p_segtree::init();
  d[0] = p_segtree::init();
  for (usize i = 0; i != N; i += 1) {
    const auto &[X, Y] = towns[i];
    const usize pos = yc.get({Y, i});
    u[i + 1] = u[i].update(pos, -X + Y);
    d[i + 1] = d[i].update(pos, -X - Y);
  }

  std::priority_queue<pair, std::vector<pair>, std::greater<pair>> que;
  const auto push = [&](const usize i) {
    const auto &[X, Y] = towns[i];
    const usize pos = yc.get({Y, i});
    const auto [um, ui] = u[i].get_min(pos, 1 << digits);
    const auto [dm, di] = d[i].get_min(0, pos);
    if (um == INF && dm == INF) {
      return;
    }
    if (um + X - Y < dm + X + Y) {
      que.push({um + X - Y, i});
      u[i] = u[i].update(ui, INF);
    } else {
      que.push({dm + X + Y, i});
      d[i] = d[i].update(di, INF);
    }
  };

  for (usize i = 0; i != N; i += 1) {
    push(i);
  }
  for (usize k = 0; k != K; k += 1) {
    const auto [c, i] = que.top();
    que.pop();
    std::cout << c << "\n";
    push(i);
  }

  return 0;
}

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