test/queue/PerisitentQueue.test.cpp

• View this file on GitHub
• Last update: 2023-06-08 02:51:47+09:00
• Problem: https://judge.yosupo.jp/problem/persistent_queue

Depends on

• PersistentQueue - 永続queue (lib/15-queue/PersistentQueue.cpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/persistent_queue"

#include <vector>
#include <iostream>
#include <array>
#include <cassert>
#include <unordered_map>
using namespace std;
#include "../../lib/15-queue/PersistentQueue.cpp"

int main(void){
    cin.tie(0);ios::sync_with_stdio(false); 
    int Q; cin >> Q;
    PersistentQueue<int> pq(1e9+7);
    for(int i=0;i<Q;++i) {
        int q; cin >> q;
        if(q==0) {
            int t,x; cin >> t >> x;
            pq.push(t,i,x);
        }
        else {
            int t; cin >> t;
            cout << pq.pop(t,i) << "\n";
        }
    }
    return 0; 
}

#line 1 "test/queue/PerisitentQueue.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/persistent_queue"

#include <vector>
#include <iostream>
#include <array>
#include <cassert>
#include <unordered_map>
using namespace std;
#line 1 "lib/15-queue/PersistentQueue.cpp"
/*
 * @title PersistentQueue - 永続queue
 * @docs md/data-structure/PersistentQueue.md
 */
template<class T,size_t bit=20> class PersistentQueue{
private:
    struct Node{
        array<size_t,bit> parent;
        T val;
        size_t length;
        Node(T val,size_t length):val(val),length(length){}
    };
    vector<Node> tree;
    unordered_map<int,size_t> mp;
public:
    PersistentQueue(T inf) {
        Node root(inf,0);
        for(size_t i=0;i<bit;++i) root.parent[i]=0;
        mp[-1]=0;
        tree.push_back(root);
    }
    void push(int target_id, int pushed_id, T val) {
        size_t idx = mp[target_id];
        size_t length = tree[idx].length + 1;
        Node leaf(val,length);
        leaf.parent[0]=idx;
        for(size_t i=1;i<bit;++i) leaf.parent[i]=tree[leaf.parent[i-1]].parent[i-1];
        mp[pushed_id] = tree.size();
        tree.push_back(leaf);
    }
    T pop(int target_id,int pushed_id) {
        size_t idx = mp[target_id];
        auto node = tree[idx];
        size_t& length = node.length;
        assert(length > 0);
        length-=1;
        mp[pushed_id] = tree.size();
        tree.push_back(node);
        for(int i=bit-1; 0<=i; --i) if((length>>i) & 1) idx = tree[idx].parent[i];
        return tree[idx].val;
    }
};
#line 10 "test/queue/PerisitentQueue.test.cpp"

int main(void){
    cin.tie(0);ios::sync_with_stdio(false); 
    int Q; cin >> Q;
    PersistentQueue<int> pq(1e9+7);
    for(int i=0;i<Q;++i) {
        int q; cin >> q;
        if(q==0) {
            int t,x; cin >> t >> x;
            pq.push(t,i,x);
        }
        else {
            int t; cin >> t;
            cout << pq.pop(t,i) << "\n";
        }
    }
    return 0; 
}

Back to top page