Submit Info #26959

Problem Lang User Status Time Memory
Persistent Queue cpp Forested AC 263 ms 158.80 MiB

ケース詳細
Name Status Time Memory
ephemeral_00 AC 194 ms 90.52 MiB
example_00 AC 2 ms 0.68 MiB
half_rot_killer_00 AC 195 ms 101.95 MiB
random_00 AC 131 ms 37.98 MiB
random_01 AC 166 ms 44.93 MiB
random_02 AC 16 ms 5.67 MiB
random_2_00 AC 146 ms 45.41 MiB
random_2_01 AC 176 ms 53.92 MiB
random_2_02 AC 19 ms 6.71 MiB
random_3_00 AC 195 ms 114.92 MiB
random_3_01 AC 226 ms 137.03 MiB
random_3_02 AC 26 ms 13.87 MiB
two_stacks_killer_00 AC 263 ms 158.80 MiB

// Template #define FORESTED #include "bits/stdc++.h" #define rep_override(x, y, z, name, ...) name #define rep2(i, n) for (int i = 0; i < (int)(n); ++i) #define rep3(i, l, r) for (int i = (int)(l); i < (int)(r); ++i) #define rep(...) rep_override(__VA_ARGS__, rep3, rep2)(__VA_ARGS__) #define per(i, n) for (ll i = (ll)(n) - 1; i >= 0; --i) #define all(x) (x).begin(), (x).end() using namespace std; using ll = long long; constexpr int inf = 1001001001; constexpr ll INF = 3003003003003003003LL; template <typename T> inline bool chmin(T &x, const T &y) { if (x > y) { x = y; return true; } return false; } template <typename T> inline bool chmax(T &x, const T &y) { if (x < y) { x = y; return true; } return false; } struct IOSET { IOSET() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); } } ioset; template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (T &element : vec) is >> element; return is; } template <typename T> vector<T> operator--(vector<T> &vec) { for (T &element : vec) --element; return vec; } // Presistent Array #ifndef FORESTED #include "template.cpp" #endif #define PERSISTENT_ARRAY template <typename T> class PersistentArray { static const int children_size = 4; struct Node { T data; Node *children[children_size] = {}; }; Node *root; T get(Node *t, int idx) { assert(t != nullptr); if (idx == 0) return t -> data; return get(t -> children[idx % children_size], idx / children_size); } Node *set(Node *t, int idx, const T &x) { Node *res = new Node(); if (t != nullptr) { memcpy(res -> children, t -> children, sizeof(t -> children)); res -> data = t -> data; } if (idx == 0) res -> data = x; else res -> children[idx % children_size] = set(res -> children[idx % children_size], idx / children_size, x); return res; } public: PersistentArray() : root(nullptr) {} T get(int idx) { assert(idx >= 0); return get(root, idx); } void set(int idx, const T &x) { assert(idx >= 0); root = set(root, idx, x); } }; // Main int main() { int q; cin >> q; vector<PersistentArray<int>> qs(q + 1); vector<int> top(q + 1, 0), size(q + 1, 0); rep(i, 1, q + 1) { int type, t; cin >> type >> t; ++t; qs[i] = qs[t]; top[i] = top[t]; size[i] = size[t]; if (type == 0) { int x; cin >> x; qs[i].set(size[i], x); ++size[i]; } else { cout << qs[i].get(top[i]) << "\n"; ++top[i]; } } }