tests/median_heap.test.cpp

• View this file on GitHub
• Last update: 2025-01-23 04:00:37+00:00
• Problem: https://atcoder.jp/contests/abc127/tasks/abc127_f

Depends on

• Heap managing median (tools/median_heap.hpp)

Code

// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc127/tasks/abc127_f
// competitive-verifier: IGNORE

#include <iostream>
#include "tools/median_heap.hpp"

using ll = long long;

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

  ll Q;
  std::cin >> Q;

  tools::median_heap<ll> heap;
  ll min = 0;
  for (ll i = 0; i < Q; ++i) {
    ll t;
    std::cin >> t;
    if (t == 1) {
      ll a, b;
      std::cin >> a >> b;

      const bool uses_prev_median = heap.size() % 2 == 1 && a < heap.lesser();
      if (uses_prev_median) {
        min += std::abs(heap.lesser() - a) + b;
      }
      heap.push(a);
      if (!uses_prev_median) {
        min += std::abs(heap.lesser() - a) + b;
      }
    } else {
      std::cout << heap.lesser() << ' ' << min << '\n';
    }
  }

  return 0;
}

#line 1 "tests/median_heap.test.cpp"
// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc127/tasks/abc127_f
// competitive-verifier: IGNORE

#include <iostream>
#line 1 "tools/median_heap.hpp"



#include <functional>
#include <queue>
#include <vector>
#include <cstddef>
#include <cassert>

namespace tools {

  template <typename T, typename Compare = ::std::less<T>>
  class median_heap {
  private:
    class RevCompare {
    private:
      Compare m_less;
    public:
      explicit RevCompare(const Compare& less) : m_less(less) {
      }
      bool operator()(const T& x, const T& y) const {
        return this->m_less(y, x);
      }
    };

    Compare m_less;
    ::std::priority_queue<T, ::std::vector<T>, Compare> m_pq1;
    ::std::priority_queue<T, ::std::vector<T>, RevCompare> m_pq2;

  public:
    explicit median_heap(const Compare& less) : m_less(less), m_pq1(less), m_pq2(RevCompare(less)) {
    }
    median_heap() : median_heap(Compare()) {
    }
    median_heap(const ::tools::median_heap<T, Compare>&) = default;
    median_heap(::tools::median_heap<T, Compare>&&) = default;
    ~median_heap() = default;
    ::tools::median_heap<T, Compare>& operator=(const ::tools::median_heap<T, Compare>&) = default;
    ::tools::median_heap<T, Compare>& operator=(::tools::median_heap<T, Compare>&&) = default;

    bool empty() const {
      return this->m_pq1.empty() && this->m_pq2.empty();
    }

    ::std::size_t size() const {
      return this->m_pq1.size() + this->m_pq2.size();
    }

    T lesser() const {
      assert(!this->empty());
      return this->m_pq1.top();
    }

    T greater() const {
      assert(!this->empty());
      return this->m_pq1.size() == this->m_pq2.size() ? this->m_pq2.top() : this->m_pq1.top();
    }

    void push(const T& v) {
      if (this->m_pq1.size() == this->m_pq2.size()) {
        if (!this->m_pq2.empty() && this->m_less(this->m_pq2.top(), v)) {
          this->m_pq1.push(this->m_pq2.top());
          this->m_pq2.pop();
          this->m_pq2.push(v);
        } else {
          this->m_pq1.push(v);
        }
      } else {
        if (this->m_less(v, this->m_pq1.top())) {
          this->m_pq2.push(this->m_pq1.top());
          this->m_pq1.pop();
          this->m_pq1.push(v);
        } else {
          this->m_pq2.push(v);
        }
      }
    }

    template <typename... Args>
    void emplace(Args&&... args) {
      this->push(T(::std::forward<Args>(args)...));
    }

    void swap(::tools::median_heap<T, Compare>& other) {
      ::std::swap(this->m_less, other.m_less);
      this->m_pq1.swap(other.m_pq1);
      this->m_pq2.swap(other.m_pq2);
    }
  };
}


#line 6 "tests/median_heap.test.cpp"

using ll = long long;

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

  ll Q;
  std::cin >> Q;

  tools::median_heap<ll> heap;
  ll min = 0;
  for (ll i = 0; i < Q; ++i) {
    ll t;
    std::cin >> t;
    if (t == 1) {
      ll a, b;
      std::cin >> a >> b;

      const bool uses_prev_median = heap.size() % 2 == 1 && a < heap.lesser();
      if (uses_prev_median) {
        min += std::abs(heap.lesser() - a) + b;
      }
      heap.push(a);
      if (!uses_prev_median) {
        min += std::abs(heap.lesser() - a) + b;
      }
    } else {
      std::cout << heap.lesser() << ' ' << min << '\n';
    }
  }

  return 0;
}

Back to top page