sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM "https://judge.yosupo.jp/problem/persistent_queue" #include "../../data-structure/persistent_queue.hpp" #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int Q; cin >> Q; PersistentQueue<int> init; vector<PersistentQueue<int>> ver(Q); for (int i = 0; i < Q; ++i) { int q, t; cin >> q >> t; if (q == 0) { int x; cin >> x; if (t == -1) ver[i] = init.push(x); else ver[i] = ver[t].push(x); } else { cout << ver[t].front() << "\n"; ver[i] = ver[t].pop(); } } }
#line 1 "test/yosupo/persistent_queue.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/persistent_queue" #line 2 "data-structure/persistent_queue.hpp" #include <cassert> #line 2 "data-structure/persistent_array.hpp" #include <memory> #include <vector> template <typename T, int B = 2> class PersistentArray { public: PersistentArray() = default; explicit PersistentArray(const std::vector<T>& v) { for (int i = 0; i < (int)v.size(); ++i) root = set(root, i, v[i]); } T get(int k) const { return get(root, k); } PersistentArray set(int k, const T& x) const { return PersistentArray(set(root, k, x)); } private: struct Node; using node_ptr = std::shared_ptr<Node>; struct Node { T val; node_ptr ch[B]; }; node_ptr root = nullptr; explicit PersistentArray(const node_ptr& root) : root(root) {} T get(const node_ptr& t, int k) const { if (k == 0) return t->val; return get(t->ch[k % B], k / B); } node_ptr set(const node_ptr& t, int k, const T& x) const { node_ptr res = t ? std::make_shared<Node>(*t) : std::make_shared<Node>(); if (k == 0) { res->val = x; } else { res->ch[k % B] = set(res->ch[k % B], k / B, x); } return res; } }; #line 5 "data-structure/persistent_queue.hpp" template <typename T> class PersistentQueue { public: PersistentQueue() : first(0), last(0) {} int size() const { return last - first; } bool empty() const { return size() == 0; } T front() const { assert(!empty()); return pa.get(first); } T back() const { assert(!empty()); return pa.get(last - 1); } PersistentQueue push(const T& val) const { return PersistentQueue(pa.set(last, val), first, last + 1); } PersistentQueue pop() const { assert(!empty()); return PersistentQueue(pa, first + 1, last); } private: PersistentArray<T> pa; int first, last; PersistentQueue(const PersistentArray<T>& pa, int first, int last) : pa(pa), first(first), last(last) {} }; #line 4 "test/yosupo/persistent_queue.test.cpp" #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int Q; cin >> Q; PersistentQueue<int> init; vector<PersistentQueue<int>> ver(Q); for (int i = 0; i < Q; ++i) { int q, t; cin >> q >> t; if (q == 0) { int x; cin >> x; if (t == -1) ver[i] = init.push(x); else ver[i] = ver[t].push(x); } else { cout << ver[t].front() << "\n"; ver[i] = ver[t].pop(); } } }