test/verify/aoj-alds-1-9-c.test.cpp

• View this file on GitHub
• Last update: 2026-08-10 10:55:59+00:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_C

Depends on

• Leftist-Heap (structure/heap/leftist-heap.hpp)

Code

// clang-format off
// competitive-verifier: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_C
// clang-format on

#include <iostream>
#include <string>

#include "../../structure/heap/leftist-heap.hpp"

using namespace std;

int main() {
  string s;
  LeftistHeap<int, false> que;
  auto root = que.make_root();
  while (cin >> s, s != "end") {
    if (s == "insert") {
      int x;
      cin >> x;
      root = que.push(root, x);
    } else {
      cout << root->key << "\n";
      root = que.pop(root);
    }
  }
}

#line 1 "test/verify/aoj-alds-1-9-c.test.cpp"
// clang-format off
// competitive-verifier: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_C
// clang-format on

#include <iostream>
#include <string>

#line 2 "structure/heap/leftist-heap.hpp"

#include <cassert>
#include <utility>

/**
 * @brief Leftist-Heap
 */
template <typename T, bool isMin = true>
struct LeftistHeap {
  struct Node {
    Node *l, *r;
    int s;
    T key;
    int idx;

    explicit Node(const T& key, int idx)
        : l(nullptr), r(nullptr), s(1), key(key), idx(idx) {}
  };

  LeftistHeap() = default;

  virtual Node* clone(Node* t) { return t; }

  Node* alloc(const T& key, int idx = -1) { return new Node(key, idx); }

  Node* meld(Node* a, Node* b) {
    if (!a || !b) return a ? a : b;
    if ((a->key < b->key) ^ isMin) std::swap(a, b);
    a = clone(a);
    a->r = meld(a->r, b);
    if (!a->l || a->l->s < a->r->s) std::swap(a->l, a->r);
    a->s = (a->r ? a->r->s : 0) + 1;
    return a;
  }

  Node* push(Node* t, const T& key, int idx = -1) {
    return meld(t, alloc(key, idx));
  }

  Node* pop(Node* t) {
    assert(t != nullptr);
    return meld(t->l, t->r);
  }

  Node* make_root() { return nullptr; }
};
#line 9 "test/verify/aoj-alds-1-9-c.test.cpp"

using namespace std;

int main() {
  string s;
  LeftistHeap<int, false> que;
  auto root = que.make_root();
  while (cin >> s, s != "end") {
    if (s == "insert") {
      int x;
      cin >> x;
      root = que.push(root, x);
    } else {
      cout << root->key << "\n";
      root = que.pop(root);
    }
  }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	2	AC	2 ms	4 MB
g++	3	AC	2 ms	4 MB
g++	4	AC	2 ms	4 MB
g++	5	AC	1242 ms	74 MB
clang++	2	AC	2 ms	4 MB
clang++	3	AC	2 ms	4 MB
clang++	4	AC	3 ms	4 MB
clang++	5	AC	1383 ms	74 MB

Back to top page