test/yosupo/persistent_queue.test.cpp

• View this file on GitHub
• Last update: 2024-07-11 22:21:57+09:00
• Problem: https://judge.yosupo.jp/problem/persistent_queue

Code

#define PROBLEM "https://judge.yosupo.jp/problem/persistent_queue"
#include <iostream> 
#include "include/mtl/persistent_queue.hpp"
#include <bits/stdc++.h>
using namespace std;

int main() {
    int q; cin>>q;
    vector<PersistentQueue<int>> S(q+1);
    for (int i = 0; i < q; i++) {
        int c; cin>>c;
        if (c == 0) {
            int t,x; cin>>t>>x; t++;
            S[i+1] = S[t].push(x);
        } else {
            int t; cin>>t; t++;
            auto v = S[t].front();
            S[i+1] = S[t].pop();
            cout << v << endl;
        }
    }
}

#line 1 "test/yosupo/persistent_queue.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/persistent_queue"
#include <iostream> 
#line 2 "include/mtl/persistent_queue.hpp"
#include <memory>
#include <cstdint>
#include <algorithm>
#include <cassert>

/**
 * @brief Persistent Queue
*/
template<class T>
class PersistentQueue {
public:
    using value_type = T;
private:
    struct Node;
    struct Stream;
    using node_ptr = std::shared_ptr<Node>;
    using raw_ptr = Node*;
    using stream_ptr = std::shared_ptr<Stream>;
    template<class... Args>
    static node_ptr make_node(Args&&... args) {
        return std::make_shared<Node>(std::forward<Args>(args)...);
    }
    template<class... Args>
    static stream_ptr make_stream(Args&&... args) {
        return std::make_shared<Stream>(std::forward<Args>(args)...);
    }
    struct Node {
        node_ptr next;
        value_type v;
        template<class N, class... Args>
        Node(N&& n, Args&&... args) 
            : next(std::forward<N>(n)), v(std::forward<Args>(args)...) {}
    };
    struct Stream {
        node_ptr scan, rotate;
        template<class Rptr>
        Stream(const node_ptr& nptr, Rptr&& rptr) 
            : scan(nptr), rotate(std::forward<Rptr>(rptr)) {}
        
        node_ptr next() {
            node_ptr ret;
            if (scan) {
                ret = make_node(nullptr, scan->v);
                scan = scan->next;
            } else {
                while (rotate) {
                    ret = make_node(ret, rotate->v);
                    rotate = rotate->next;
                }
            }
            return ret;
        }
    };

    node_ptr f_;
    raw_ptr proc_;
    stream_ptr stream_;
    size_t size_;
    node_ptr r_;

    PersistentQueue(stream_ptr&& stream, size_t size) : 
        f_(stream->next()), 
        proc_(f_.get()), 
        stream_(std::move(stream)), 
        size_(size),
        r_(nullptr) {}
    template<class Nptr>
    PersistentQueue(const node_ptr& f, const raw_ptr&& proc, const stream_ptr& stream, size_t size, 
                    Nptr&& r) 
        : f_(f), proc_(proc), stream_(stream), size_(size), r_(std::forward<Nptr>(r)) {}

    template<class... Args>
    [[nodiscard]] PersistentQueue _push(Args&&... args) const {
        if (!proc_) {
            return PersistentQueue(
                make_stream(f_, make_node(r_, std::forward<Args>(args)...)), size()+1);
        }
        if (!proc_->next) {
            proc_->next = stream_->next();
        }
        return PersistentQueue(f_, proc_->next.get(), stream_, size()+1,
                               make_node(r_, std::forward<Args>(args)...));
    }
    [[nodiscard]] PersistentQueue _pop() const {
        assert(!empty());
        if (!proc_) {
            return PersistentQueue(make_stream(f_->next, r_), size()-1);
        }
        if (!proc_->next) {
            proc_->next = stream_->next();
        }
        return PersistentQueue(f_->next, proc_->next.get(), stream_, size()-1, r_);
    }

public:
    PersistentQueue() 
        : f_(nullptr), proc_(nullptr), stream_(nullptr), size_(0), r_(nullptr) {}
    size_t size() const { return size_; }
    bool empty() const { return size() == 0; }
    const value_type& front() const {
        assert(f_);
        return f_->v;
    }
    template<class V>
    [[nodiscard]] PersistentQueue push(V&& x) const {
        return _push(std::forward<V>(x));
    }
    [[nodiscard]] PersistentQueue push(const T& x) const {
        return _push(x);
    }
    [[nodiscard]] PersistentQueue push(T&& x) const {
        return _push(std::move(x));
    }
    template<class... Args>
    [[nodiscard]] PersistentQueue emplace(Args&&... args) const {
        return _push(std::forward<Args>(args)...);
    }
    [[nodiscard]] PersistentQueue pop() const {
        return _pop();
    }
};
#line 4 "test/yosupo/persistent_queue.test.cpp"
#include <bits/stdc++.h>
using namespace std;

int main() {
    int q; cin>>q;
    vector<PersistentQueue<int>> S(q+1);
    for (int i = 0; i < q; i++) {
        int c; cin>>c;
        if (c == 0) {
            int t,x; cin>>t>>x; t++;
            S[i+1] = S[t].push(x);
        } else {
            int t; cin>>t; t++;
            auto v = S[t].front();
            S[i+1] = S[t].pop();
            cout << v << endl;
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	ephemeral_00	AC	438 ms	54 MB
g++	example_00	AC	6 ms	3 MB
g++	half_rot_killer2_00	AC	192 ms	64 MB
g++	half_rot_killer_00	AC	565 ms	57 MB
g++	random_00	AC	565 ms	52 MB
g++	random_01	AC	625 ms	61 MB
g++	random_02	AC	76 ms	10 MB
g++	random_2_00	AC	431 ms	52 MB
g++	random_2_01	AC	565 ms	61 MB
g++	random_2_02	AC	59 ms	10 MB
g++	random_3_00	AC	408 ms	44 MB
g++	random_3_01	AC	670 ms	52 MB
g++	random_3_02	AC	57 ms	9 MB
g++	two_stacks_killer_00	AC	466 ms	64 MB
clang++	ephemeral_00	AC	477 ms	54 MB
clang++	example_00	AC	6 ms	3 MB
clang++	half_rot_killer2_00	AC	190 ms	64 MB
clang++	half_rot_killer_00	AC	550 ms	57 MB
clang++	random_00	AC	517 ms	52 MB
clang++	random_01	AC	574 ms	61 MB
clang++	random_02	AC	115 ms	10 MB
clang++	random_2_00	AC	570 ms	52 MB
clang++	random_2_01	AC	566 ms	61 MB
clang++	random_2_02	AC	106 ms	10 MB
clang++	random_3_00	AC	449 ms	44 MB
clang++	random_3_01	AC	444 ms	52 MB
clang++	random_3_02	AC	60 ms	9 MB
clang++	two_stacks_killer_00	AC	458 ms	64 MB

Back to top page