Submit Info #45963

Problem Lang User Status Time Memory
Persistent Queue cpp ningenMe AC 371 ms 108.32 MiB

ケース詳細
Name Status Time Memory
ephemeral_00 AC 252 ms 100.25 MiB
example_00 AC 1 ms 0.70 MiB
half_rot_killer2_00 AC 194 ms 99.59 MiB
half_rot_killer_00 AC 257 ms 108.32 MiB
random_00 AC 314 ms 100.61 MiB
random_01 AC 361 ms 100.59 MiB
random_02 AC 33 ms 13.18 MiB
random_2_00 AC 318 ms 100.24 MiB
random_2_01 AC 371 ms 100.34 MiB
random_2_02 AC 35 ms 13.08 MiB
random_3_00 AC 227 ms 100.36 MiB
random_3_01 AC 259 ms 100.37 MiB
random_3_02 AC 28 ms 13.09 MiB
two_stacks_killer_00 AC 285 ms 107.12 MiB

#include <bits/stdc++.h> using namespace std; using int128 = __int128_t; using int64 = long long; using int32 = int; using uint128 = __uint128_t; using uint64 = unsigned long long; using uint32 = unsigned int; #define ALL(obj) (obj).begin(),(obj).end() template<class T> using priority_queue_reverse = priority_queue<T,vector<T>,greater<T>>; constexpr int64 MOD = 1'000'000'000LL + 7; //' constexpr int64 MOD2 = 998244353; constexpr int64 HIGHINF = 1'000'000'000'000'000'000LL; constexpr int64 LOWINF = 1'000'000'000'000'000LL; //' constexpr long double PI = 3.1415926535897932384626433L; template <class T> vector<T> multivector(size_t N,T init){return vector<T>(N,init);} template <class... T> auto multivector(size_t N,T... t){return vector<decltype(multivector(t...))>(N,multivector(t...));} template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}} template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;} template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;} template <class T>ostream &operator<<(ostream &o, const multiset<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;} template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;} template <class T>ostream &operator<<(ostream &o, const deque<T>&obj) {o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;} template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {o << "{" << obj.first << ", " << obj.second << "}"; return o;} void print(void) {cout << endl;} template <class Head> void print(Head&& head) {cout << head;print();} template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {cout << head << " ";print(forward<Tail>(tail)...);} template <class T> void chmax(T& a, const T b){a=max(a,b);} template <class T> void chmin(T& a, const T b){a=min(a,b);} vector<string> split(const string &str, const char delemiter) {vector<string> res;stringstream ss(str);string buffer; while( getline(ss, buffer, delemiter) ) res.push_back(buffer); return res;} inline constexpr int msb(int x) {return x?31-__builtin_clz(x):-1;} inline constexpr int64 ceil_div(const int64 a,const int64 b) {return (a+(b-1))/b;}// return ceil(a/b) void YN(bool flg) {cout << (flg ? "YES" : "NO") << endl;} void Yn(bool flg) {cout << (flg ? "Yes" : "No") << endl;} void yn(bool flg) {cout << (flg ? "yes" : "no") << endl;} 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; } void print() { for(auto& p:mp) { int id = p.first; size_t idx = p.second; cout << id << " " << idx << " " << tree[idx].val << " {"; for(size_t i=0;i<bit;++i) cout << " " << tree[idx].parent[i]; cout << "} " << tree[idx].length << " " << tree[idx].val << endl; } } }; /** * @url * @est */ int main() { 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; }