test/aoj/ALDS1_9_C.SkewHeap.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 11:17:48+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/9/ALDS1_9_C

Depends on

• Skew-Heap (src/DataStructure/SkewHeap.hpp)
• メンバの有無を判定するテンプレート 他 (src/Internal/HAS_CHECK.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/9/ALDS1_9_C
// competitive-verifier: TLE 1.5
// competitive-verifier: MLE 64
#include <iostream>
#include <string>
#include "src/DataStructure/SkewHeap.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 SkewHeap<int> S;
 string op;
 while (cin >> op && op != "end") {
  if (op[0] == 'i') {
   int k;
   cin >> k;
   S.push(k);
  } else cout << S.pop() << '\n';
 }
 return 0;
}

#line 1 "test/aoj/ALDS1_9_C.SkewHeap.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/9/ALDS1_9_C
// competitive-verifier: TLE 1.5
// competitive-verifier: MLE 64
#include <iostream>
#include <string>
#line 2 "src/DataStructure/SkewHeap.hpp"
#include <functional>
#include <algorithm>
#include <cstddef>
#line 2 "src/Internal/HAS_CHECK.hpp"
#include <type_traits>
#define MEMBER_MACRO(member, Dummy, name, type1, type2, last) \
 template <class tClass> struct name##member { \
  template <class U, Dummy> static type1 check(U *); \
  static type2 check(...); \
  static tClass *mClass; \
  last; \
 }
#define HAS_CHECK(member, Dummy) MEMBER_MACRO(member, Dummy, has_, std::true_type, std::false_type, static const bool value= decltype(check(mClass))::value)
#define HAS_MEMBER(member) HAS_CHECK(member, int dummy= (&U::member, 0))
#define HAS_TYPE(member) HAS_CHECK(member, class dummy= typename U::member)
#define HOGE_OR(member, name, type2) \
 MEMBER_MACRO(member, class dummy= typename U::member, name, typename U::member, type2, using type= decltype(check(mClass))); \
 template <class tClass> using name##member##_t= typename name##member<tClass>::type
#define NULLPTR_OR(member) HOGE_OR(member, nullptr_or_, std::nullptr_t)
#define MYSELF_OR(member) HOGE_OR(member, myself_or_, tClass)
#line 6 "src/DataStructure/SkewHeap.hpp"
template <typename T, typename Compare= std::less<T>, typename M= void> struct SkewHeap {
 HAS_MEMBER(mp);
 HAS_MEMBER(cp);
 HAS_TYPE(E);
 NULLPTR_OR(E);
 template <class L> using dual= std::conjunction<has_E<L>, has_mp<L>, has_cp<L>>;
 template <class tDerived> struct Node_B {
  T key;
  tDerived *ch[2];
 };
 template <bool du_, typename tEnable= void> struct Node_D: Node_B<Node_D<du_>> {};
 template <bool du_> struct Node_D<du_, typename std::enable_if_t<du_>>: Node_B<Node_D<du_>> {
  typename M::E lazy;
  bool lazy_flg= false;
 };
 using Node= Node_D<dual<M>::value>;
 using E= nullptr_or_E_t<M>;
 Node *root;
 static inline void propagate(Node *&t, const E &x) {
  if (!t) return;
  t->lazy_flg ? (M::cp(t->lazy, x), x) : (t->lazy= x);
  M::mp(t->key, x), t->lazy_flg= true;
 }
 static inline void push(Node *t) {
  if (t->lazy_flg) propagate(t->ch[0], t->lazy), propagate(t->ch[1], t->lazy), t->lazy_flg= false;
 }
 Node *merge(Node *a, Node *b) {
  if (!a || !b) return a ? a : b;
  if (Compare()(a->key, b->key)) std::swap(a, b);
  if constexpr (dual<M>::value) push(a);
  return std::swap(a->ch[0], a->ch[1]= merge(b, a->ch[1])), a;
 }
public:
 /* max heap */ SkewHeap(): root(nullptr) {}
 void push(T key) { root= merge(root, new Node{key}); }
 T pop() {
  T ret= root->key;
  if constexpr (dual<M>::value) push(root);
  return root= merge(root->ch[0], root->ch[1]), ret;
 }
 T top() { return root->key; }
 bool empty() { return !root; }
 void apply(E v) {
  static_assert(dual<M>::value, "\"apply\" is not available\n");
  propagate(root, v);
 }
 SkewHeap &operator+=(SkewHeap r) { return root= merge(root, r.root), *this; }
 SkewHeap operator+(SkewHeap r) { return SkewHeap(*this)+= r; }
};
#line 7 "test/aoj/ALDS1_9_C.SkewHeap.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 SkewHeap<int> S;
 string op;
 while (cin >> op && op != "end") {
  if (op[0] == 'i') {
   int k;
   cin >> k;
   S.push(k);
  } else cout << S.pop() << '\n';
 }
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	2.in	AC	7 ms	4 MB
g++-13	3.in	AC	6 ms	4 MB
g++-13	4.in	AC	6 ms	4 MB
g++-13	5.in	AC	747 ms	50 MB
clang++-18	2.in	AC	6 ms	4 MB
clang++-18	3.in	AC	5 ms	4 MB
clang++-18	4.in	AC	5 ms	4 MB
clang++-18	5.in	AC	947 ms	51 MB

Back to top page