oj.uz

Submission #386289

# Submission time Handle Problem Language Result Execution time Memory
386289 2021-04-06T09:47:16 Z model_code Road Construction (JOI21_road_construction) C++17
100 / 100
 3578 ms 922324 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 806 ms 228844 KB Output is correct
2 Correct 818 ms 228844 KB Output is correct
3 Correct 723 ms 227052 KB Output is correct
4 Correct 684 ms 227052 KB Output is correct
5 Correct 737 ms 227692 KB Output is correct
6 Correct 10 ms 4972 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2074 ms 921428 KB Output is correct
2 Correct 2045 ms 921316 KB Output is correct
3 Correct 545 ms 226924 KB Output is correct
4 Correct 1668 ms 921060 KB Output is correct
5 Correct 1592 ms 921324 KB Output is correct
6 Correct 1588 ms 921468 KB Output is correct
7 Correct 1672 ms 920916 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2062 ms 697032 KB Output is correct
2 Correct 2048 ms 697052 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1056 ms 697172 KB Output is correct
5 Correct 1509 ms 697088 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2062 ms 697032 KB Output is correct
2 Correct 2048 ms 697052 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1056 ms 697172 KB Output is correct
5 Correct 1509 ms 697088 KB Output is correct
6 Correct 2020 ms 697056 KB Output is correct
7 Correct 2064 ms 697012 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 2045 ms 697016 KB Output is correct
11 Correct 1073 ms 697104 KB Output is correct
12 Correct 1503 ms 697052 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 806 ms 228844 KB Output is correct
2 Correct 818 ms 228844 KB Output is correct
3 Correct 723 ms 227052 KB Output is correct
4 Correct 684 ms 227052 KB Output is correct
5 Correct 737 ms 227692 KB Output is correct
6 Correct 10 ms 4972 KB Output is correct
7 Correct 2142 ms 504468 KB Output is correct
8 Correct 2136 ms 504208 KB Output is correct
9 Correct 712 ms 227052 KB Output is correct
10 Correct 1501 ms 503392 KB Output is correct
11 Correct 1755 ms 503320 KB Output is correct
12 Correct 1167 ms 504292 KB Output is correct
13 Correct 1280 ms 502576 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 806 ms 228844 KB Output is correct
2 Correct 818 ms 228844 KB Output is correct
3 Correct 723 ms 227052 KB Output is correct
4 Correct 684 ms 227052 KB Output is correct
5 Correct 737 ms 227692 KB Output is correct
6 Correct 10 ms 4972 KB Output is correct
7 Correct 2074 ms 921428 KB Output is correct
8 Correct 2045 ms 921316 KB Output is correct
9 Correct 545 ms 226924 KB Output is correct
10 Correct 1668 ms 921060 KB Output is correct
11 Correct 1592 ms 921324 KB Output is correct
12 Correct 1588 ms 921468 KB Output is correct
13 Correct 1672 ms 920916 KB Output is correct
14 Correct 2062 ms 697032 KB Output is correct
15 Correct 2048 ms 697052 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1056 ms 697172 KB Output is correct
18 Correct 1509 ms 697088 KB Output is correct
19 Correct 2020 ms 697056 KB Output is correct
20 Correct 2064 ms 697012 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 2045 ms 697016 KB Output is correct
24 Correct 1073 ms 697104 KB Output is correct
25 Correct 1503 ms 697052 KB Output is correct
26 Correct 2142 ms 504468 KB Output is correct
27 Correct 2136 ms 504208 KB Output is correct
28 Correct 712 ms 227052 KB Output is correct
29 Correct 1501 ms 503392 KB Output is correct
30 Correct 1755 ms 503320 KB Output is correct
31 Correct 1167 ms 504292 KB Output is correct
32 Correct 1280 ms 502576 KB Output is correct
33 Correct 3578 ms 922188 KB Output is correct
34 Correct 3569 ms 922080 KB Output is correct
35 Correct 2765 ms 921436 KB Output is correct
36 Correct 2138 ms 921948 KB Output is correct
37 Correct 2161 ms 922324 KB Output is correct
38 Correct 2389 ms 920668 KB Output is correct