Submit Info #28774

Problem Lang User Status Time Memory
Persistent Queue cpp beet AC 583 ms 769.55 MiB

ケース詳細
Name Status Time Memory
ephemeral_00 AC 413 ms 502.49 MiB
example_00 AC 2 ms 0.67 MiB
half_rot_killer2_00 AC 282 ms 346.55 MiB
half_rot_killer_00 AC 520 ms 656.05 MiB
random_00 AC 198 ms 92.92 MiB
random_01 AC 241 ms 111.40 MiB
random_02 AC 22 ms 13.30 MiB
random_2_00 AC 222 ms 107.93 MiB
random_2_01 AC 270 ms 132.22 MiB
random_2_02 AC 25 ms 15.15 MiB
random_3_00 AC 338 ms 395.30 MiB
random_3_01 AC 402 ms 477.17 MiB
random_3_02 AC 43 ms 44.73 MiB
two_stacks_killer_00 AC 583 ms 769.55 MiB

#define PROBLEM "https://judge.yosupo.jp/problem/persistent_queue" #include<bits/stdc++.h> using namespace std; #define call_from_test #ifndef call_from_test #include <bits/stdc++.h> using namespace std; #endif //BEGIN CUT HERE template<typename Impl, typename Data, typename Node, size_t LIM> struct RBST{ using u32 = uint32_t; u32 xor128(){ static u32 x = 123456789; static u32 y = 362436069; static u32 z = 521288629; static u32 w = 88675123; u32 t = x ^ (x << 11); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); } alignas(Node) static inline char pool[sizeof(Node)*LIM]; static inline Node* ptr = (Node*)pool; static inline size_t size; template<typename... Args> inline Node* create(Args&&... args){ return new (ptr+size++) Node(std::forward<Args>(args)...); } inline size_t count(const Node *t){return Data::count(t);} inline Node* touch(Node *t){ return static_cast<Impl*>(this)->touch(t); } inline void toggle(Node *t){ return static_cast<Impl*>(this)->toggle(t); } inline Node* pushup(Node *t){ return static_cast<Impl*>(this)->pushup(t); } Node* toggle(Node *a,size_t l,size_t r){ auto s=split(a,l); auto t=split(s.second,r-l); auto u=touch(t.first); toggle(u); return merge(s.first,merge(u,t.second)); } Node* merge(Node* a,Node* b){ if(a==nullptr) return b; if(b==nullptr) return a; if(xor128()%(count(a)+count(b))<count(a)){ a=touch(a); a->r=merge(a->r,b); a->r->p=a; return pushup(a); } b=touch(b); b->l=merge(a,b->l); b->l->p=b; return pushup(b); } pair<Node*, Node*> split(Node* a,size_t k){ if(a==nullptr) return make_pair(a,a); a=touch(a); if(k<=count(a->l)){ if(a->l) a->l->p=nullptr; auto s=split(a->l,k); a->l=s.second; if(a->l) a->l->p=a; return make_pair(s.first,pushup(a)); } if(a->r) a->r->p=nullptr; auto s=split(a->r,k-(count(a->l)+1)); a->r=s.first; if(a->r) a->r->p=a; return make_pair(pushup(a),s.second); } Node* insert(Node *a,size_t k,Node v){ Node* b=create(v); auto s=split(a,k); return merge(merge(s.first,b),s.second); } Node* erase(Node *a,size_t k){ assert(k<count(a)); auto s=split(a,k); auto t=split(s.second,1); return merge(s.first,t.second); } Node* find_by_order(Node *a,size_t k){ assert(k<count(a)); a=touch(a); size_t num=count(a->l); if(k<num) return find_by_order(a->l,k); if(k>num) return find_by_order(a->r,k-(num+1)); return a; } inline bool is_right(Node* a){ return a->p and a->p->r==a; } size_t order_of_key(Node* a){ size_t res=count(a->l); while(a){ if(is_right(a)) res+=count(a->p->l)+1; a=a->p; } return res; } Node* build(size_t l,size_t r,const vector<Node> &vs){ if(l+1==r) return create(vs[l]); size_t m=(l+r)>>1; return merge(build(l,m,vs),build(m,r,vs)); } Node* build(const vector<Node> &vs){ return build(0,vs.size(),vs); } template<typename T> Node* set_val(Node *a,size_t k,T val){ assert(k<count(a)); a=touch(a); size_t num=count(a->l); if(k<num) a->l=set_val(a->l,k,val); if(k>num) a->r=set_val(a->r,k-(num+1),val); if(k==num) a->val=val; return pushup(a); } Node* get_val(Node *a,size_t k){ assert(k<count(a)); a=touch(a); size_t num=count(a->l); if(k<num) return get_val(a->l,k); if(k>num) return get_val(a->r,k-(num+1)); return a; } template<typename E> Node* update(Node *a,size_t l,size_t r,E v){ auto s=split(a,l); auto t=split(s.second,r-l); auto u=touch(t.first); propagate(u,v); return merge(s.first,merge(u,t.second)); } decltype(auto) query(Node *&a,size_t l,size_t r){ auto s=split(a,l); auto t=split(s.second,r-l); auto u=t.first; auto res=static_cast<Impl*>(this)->query(u); a=merge(s.first,merge(u,t.second)); return res; } }; //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #ifndef call_from_test #include <bits/stdc++.h> using namespace std; #endif //BEGIN CUT HERE template<typename T> struct Array{ struct Node{ Node *l,*r,*p; size_t cnt; bool rev; T val; Node(T val): cnt(1),rev(0),val(val){l=r=p=nullptr;} }; static inline size_t count(const Node *t){ return t?t->cnt:0; } inline void toggle(Node *t){ swap(t->l,t->r); t->rev^=1; } inline bool dirty(Node *t){ return t->rev; } inline Node* eval(Node* t){ if(t->rev){ if(t->l) toggle(t->l); if(t->r) toggle(t->r); t->rev=false; } return t; } inline Node* pushup(Node *t){ t->cnt=count(t->l)+1+count(t->r); return t; } inline T reflect(Node *t){ assert(t); return t->val; } void dump(typename vector<Node>::iterator it,Node* const t,bool rev){ if(!count(t)) return; Node *l=t->l,*r=t->r; if(rev) swap(l,r); rev^=t->rev; dump(it,l,rev); *(it+count(l))=Node(t->val); dump(it+count(l)+1,r,rev); } vector<Node> dump(Node* t){ assert(t!=nullptr); vector<Node> vs(count(t),*t); dump(vs.begin(),t,false); return vs; } }; //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #ifndef call_from_test #include <bits/stdc++.h> using namespace std; #define call_from_test #include "../rbst.cpp" #undef call_from_test #endif //BEGIN CUT HERE template<typename Data, size_t LIM> struct Persistent : RBST<Persistent<Data, LIM>, Data, typename Data::Node, LIM>{ using super = RBST<Persistent, Data, typename Data::Node, LIM>; using Node = typename Data::Node; Data data; template<class... Args> Persistent(Args... args):data(forward<Args>(args)...){} inline Node* clone(Node *t){ if(t==nullptr) return t; return super::create(*t); } inline Node* touch(Node *t){ if(t==nullptr) return t; t=clone(t); if(data.dirty(t)){ t->l=clone(t->l); t->l=clone(t->r); } return data.eval(t); } using super::toggle; inline void toggle(Node *t){return data.toggle(t);} inline Node* pushup(Node *t){return data.pushup(t);} inline decltype(auto) get_val(Node *a,size_t k){ return data.reflect(super::get_val(a,k)); } using super::query; inline decltype(auto) query(Node *a){ return data.reflect(a); } bool almost_full() const{ return super::size+1000>LIM; } Node* rebuild(Node* a){ auto vs=data.dump(a); super::size=0; return super::build(vs); } }; //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #undef call_from_test #ifdef SANITIZE #define IGNORE #endif signed main(){ cin.tie(0); ios::sync_with_stdio(0); const char newl = '\n'; using Data = Array<int>; using Node = Data::Node; const int LIM = 2e7; Persistent<Data, LIM> pa; Node* rt=pa.create(0); int q; cin>>q; vector<Node*> ss(q,nullptr); for(int i=0;i<q;i++){ int a; cin>>a; if(a==0){ int t,x; cin>>t>>x; Node* p=~t?ss[t]:rt; ss[i]=pa.insert(p,p->cnt,Node(x)); } if(a==1){ int t; cin>>t; cout<<pa.get_val(ss[t],1)<<newl; ss[i]=pa.erase(ss[t],1); } } return 0; }