Submission #363779

#	Time	Username	Problem	Language	Result	Execution time	Memory
363779		KoD	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	162 ms	9204 KiB

bridge

#line 1 "main.cpp"

/**
 * @title Template
 */

#include <iostream>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>
#include <cassert>
#include <queue>

#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"

#line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"

class range {
  struct iter {
    std::size_t itr;
    constexpr iter(std::size_t pos) noexcept: itr(pos) { }
    constexpr void operator ++ () noexcept { ++itr; }
    constexpr bool operator != (iter other) const noexcept { return itr != other.itr; }
    constexpr std::size_t operator * () const noexcept { return itr; }
  };

  struct reviter {
    std::size_t itr;
    constexpr reviter(std::size_t pos) noexcept: itr(pos) { }
    constexpr void operator ++ () noexcept { --itr; }
    constexpr bool operator != (reviter other) const noexcept { return itr != other.itr; }
    constexpr std::size_t operator * () const noexcept { return itr; }
  };

  const iter first, last;

public:
  constexpr range(std::size_t first, std::size_t last) noexcept: first(first), last(std::max(first, last)) { }
  constexpr iter begin() const noexcept { return first; }
  constexpr iter end() const noexcept { return last; }
  constexpr reviter rbegin() const noexcept { return reviter(*last - 1); } 
  constexpr reviter rend() const noexcept { return reviter(*first - 1); } 
};

/**
 * @title Range
 */
#line 16 "main.cpp"

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

template <class T, T Div = 2>
constexpr T infty = std::numeric_limits<T>::max() / Div;

template <class T>
using Vec = std::vector<T>;

Vec<i64> solve(const Vec<std::pair<i64, i64>> &vec) {
  std::priority_queue<i64> left;
  left.push(-infty<i64>);
  std::priority_queue<i64, Vec<i64>, std::greater<i64>> right;
  right.push(infty<i64>);
  Vec<i64> ret(vec.size() + 1);
  i64 sum = 0;
  for (auto i: range(0, vec.size())) {
    const auto [s, t] = vec[i];
    if (s <= right.top()) {
      left.push(s);
      sum -= s;
    }
    else {
      right.push(s);
      sum += s;
    }
    if (t <= right.top()) {
      left.push(t);
      sum -= t;
    }
    else {
      right.push(t);
      sum += t;
    }
    while (left.size() > right.size()) {
      const auto x = left.top();
      left.pop();
      sum += x;
      right.push(x);
      sum += x;
    }
    while (left.size() + 1 < right.size()) {
      const auto x = right.top();
      right.pop();
      sum -= x;
      left.push(x);
      sum -= x;
    }
    const auto med = right.top();
    ret[i + 1] = sum + med * left.size() - med * right.size();
  }
  return ret;
}

int main() {
  usize K, N;
  std::cin >> K >> N;
  Vec<std::pair<i64, i64>> vec;
  vec.reserve(N);
  i64 base_cost = 0;
  while (N--) {
    char p, q;
    i64 s, t;
    std::cin >> p >> s >> q >> t;
    if (p == q) {
      base_cost += std::abs(s - t);
    }
    else {
      vec.emplace_back(s, t);
      base_cost += 1;
    }
  }
  std::sort(vec.begin(), vec.end(), [&](const auto &p, const auto &q) {
    return p.first + p.second < q.first + q.second;
  });
  const auto pref = solve(vec);
  i64 answer = pref.back();
  if (K == 2) {
    std::reverse(vec.begin(), vec.end());
    const auto suff = solve(vec);
    for (auto i: range(0, vec.size())) {
      answer = std::min(answer, pref[i] + suff[vec.size() - i]);
    }
  }
  std::cout << base_cost + answer << '\n';
  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37