tests/persistent_queue.test.cpp

• View this file on GitHub
• Last update: 2025-01-22 03:51:11+00:00
• Problem: https://judge.yosupo.jp/problem/persistent_queue

Depends on

• Persistent queue (tools/persistent_queue.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/persistent_queue

#include <iostream>
#include <vector>
#include "tools/persistent_queue.hpp"

using ll = long long;

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

  tools::persistent_queue<ll>::buffer buffer;
  std::vector<tools::persistent_queue<ll>> S;
  S.emplace_back(buffer);
  ll Q;
  std::cin >> Q;
  for (ll q = 0; q < Q; ++q) {
    ll type;
    std::cin >> type;
    if (type == 0) {
      ll t, x;
      std::cin >> t >> x;
      ++t;
      S.push_back(S[t].push(x));
    } else {
      ll t;
      std::cin >> t;
      ++t;
      std::cout << S[t].front() << '\n';
      S.push_back(S[t].pop());
    }
  }

  return 0;
}

#line 1 "tests/persistent_queue.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/persistent_queue

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



#line 5 "tools/persistent_queue.hpp"
#include <cstddef>
#include <limits>
#include <cassert>
#include <type_traits>

namespace tools {
  template <typename T>
  class persistent_queue {
  private:
    struct node {
      ::std::vector<::std::size_t> ancestors;
      ::std::size_t depth;
      T value;
    };

  public:
    class buffer {
    private:
      ::std::vector<::tools::persistent_queue<T>::node> m_nodes;

    public:
      buffer() = default;
      buffer(const ::tools::persistent_queue<T>::buffer&) = default;
      buffer(::tools::persistent_queue<T>::buffer&&) = default;
      ~buffer() = default;
      ::tools::persistent_queue<T>::buffer& operator=(const ::tools::persistent_queue<T>::buffer&) = default;
      ::tools::persistent_queue<T>::buffer& operator=(::tools::persistent_queue<T>::buffer&&) = default;

      friend ::tools::persistent_queue<T>;
    };

  private:
    static const ::std::size_t EMPTY = ::std::numeric_limits<::std::size_t>::max();
    ::tools::persistent_queue<T>::buffer *m_buffer;
    ::std::size_t m_front;
    ::std::size_t m_back;

    persistent_queue(::tools::persistent_queue<T>::buffer& buffer, const ::std::size_t front, const ::std::size_t back) : m_buffer(&buffer), m_front(front), m_back(back) {
    }

  public:
    persistent_queue() = default;
    persistent_queue(const ::tools::persistent_queue<T>&) = default;
    persistent_queue(::tools::persistent_queue<T>&&) = default;
    ~persistent_queue() = default;
    ::tools::persistent_queue<T>& operator=(const ::tools::persistent_queue<T>&) = default;
    ::tools::persistent_queue<T>& operator=(::tools::persistent_queue<T>&&) = default;

    explicit persistent_queue(::tools::persistent_queue<T>::buffer& buffer) : m_buffer(&buffer), m_front(EMPTY), m_back(EMPTY) {
    }

    bool empty() const {
      return this->m_front == EMPTY && this->m_back == EMPTY;
    }

    ::std::size_t size() const {
      return this->empty() ? 0 : this->m_buffer->m_nodes[this->m_back].depth - this->m_buffer->m_nodes[this->m_front].depth + 1;
    }

    T front() const {
      assert(!this->empty());
      return this->m_buffer->m_nodes[this->m_front].value;
    }

    T back() const {
      assert(!this->empty());
      return this->m_buffer->m_nodes[this->m_back].value;
    }

    ::tools::persistent_queue<T> push(const T& x) const {
      this->m_buffer->m_nodes.emplace_back();
      this->m_buffer->m_nodes.back().depth = this->empty() ? 0 : this->m_buffer->m_nodes[this->m_back].depth + 1;
      this->m_buffer->m_nodes.back().value = x;
      if (!this->empty()) {
        ::std::size_t i = 0;
        ::std::size_t v = this->m_back;
        while (true) {
          this->m_buffer->m_nodes.back().ancestors.push_back(v);
          if (this->m_buffer->m_nodes[v].ancestors.size() <= i) break;
          v = this->m_buffer->m_nodes[v].ancestors[i];
          ++i;
        }
      }
      return ::tools::persistent_queue<T>(*this->m_buffer, this->empty() ? this->m_buffer->m_nodes.size() - 1 : this->m_front, this->m_buffer->m_nodes.size() - 1);
    }

    ::tools::persistent_queue<T> pop() const {
      assert(!this->empty());
      if (this->size() == 1) {
        return ::tools::persistent_queue<T>(*this->m_buffer, EMPTY, EMPTY);
      }
      ::std::size_t v = this->m_back;
      for (::std::size_t d = this->size() - 2, i = 0; d > 0; d /= 2, ++i) {
        if (d % 2 == 1) {
          v = this->m_buffer->m_nodes[v].ancestors[i];
        }
      }
      return ::tools::persistent_queue<T>(*this->m_buffer, v, this->m_back);
    }

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


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

using ll = long long;

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

  tools::persistent_queue<ll>::buffer buffer;
  std::vector<tools::persistent_queue<ll>> S;
  S.emplace_back(buffer);
  ll Q;
  std::cin >> Q;
  for (ll q = 0; q < Q; ++q) {
    ll type;
    std::cin >> type;
    if (type == 0) {
      ll t, x;
      std::cin >> t >> x;
      ++t;
      S.push_back(S[t].push(x));
    } else {
      ll t;
      std::cin >> t;
      ++t;
      std::cout << S[t].front() << '\n';
      S.push_back(S[t].pop());
    }
  }

  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	ephemeral_00	AC	168 ms	65 MB
g++	example_00	AC	5 ms	4 MB
g++	half_rot_killer2_00	AC	172 ms	109 MB
g++	half_rot_killer_00	AC	177 ms	71 MB
g++	random_00	AC	128 ms	29 MB
g++	random_01	AC	167 ms	34 MB
g++	random_02	AC	21 ms	7 MB
g++	random_2_00	AC	154 ms	45 MB
g++	random_2_01	AC	193 ms	46 MB
g++	random_2_02	AC	24 ms	8 MB
g++	random_3_00	AC	162 ms	70 MB
g++	random_3_01	AC	191 ms	73 MB
g++	random_3_02	AC	26 ms	13 MB
g++	two_stacks_killer_00	AC	227 ms	110 MB

Back to top page