Submit Info #36697

Problem Lang User Status Time Memory
Persistent Queue cpp Forested AC 1538 ms 490.52 MiB

ケース詳細
Name Status Time Memory
ephemeral_00 AC 1150 ms 279.75 MiB
example_00 AC 0 ms 0.49 MiB
half_rot_killer2_00 AC 1076 ms 466.72 MiB
half_rot_killer_00 AC 1085 ms 317.76 MiB
random_00 AC 599 ms 96.08 MiB
random_01 AC 706 ms 114.52 MiB
random_02 AC 66 ms 13.54 MiB
random_2_00 AC 634 ms 115.64 MiB
random_2_01 AC 765 ms 139.23 MiB
random_2_02 AC 69 ms 15.64 MiB
random_3_00 AC 926 ms 347.01 MiB
random_3_01 AC 1114 ms 416.51 MiB
random_3_02 AC 105 ms 39.66 MiB
two_stacks_killer_00 AC 1538 ms 490.52 MiB

#include <array> #include <memory> #include <cassert> template <typename T, int S> class PersistentArray { struct Node; using Pointer = std::shared_ptr<Node>; struct Node { T value; std::array<Pointer, S> children; }; T get(Pointer p, int idx) { // assert(p); if (idx == 0) { return p->value; } else { return get(p->children[idx % S], idx / S); } } Pointer set(Pointer p, int idx, T value) { Pointer ret(new Node); if (p) { ret->value = p->value; ret->children = p->children; } if (idx == 0) { ret->value = value; } else { ret->children[idx % S] = set(ret->children[idx % S], idx / S, value); } return ret; } Pointer root; PersistentArray(Pointer r) : root(r) {} public: PersistentArray() {} T get(int idx) { return get(root, idx); } PersistentArray set(int idx, T value) { return PersistentArray(set(root, idx, value)); } }; #include <iostream> #include <vector> int main() { int q; std::cin >> q; using Array = PersistentArray<int, 2>; std::vector<Array> arrays(1); std::vector<int> be({0}), ed({0}); while (q--) { int ty; std::cin >> ty; if (ty == 0) { int t, x; std::cin >> t >> x; arrays.push_back(arrays[t + 1].set(ed[t + 1], x)); be.push_back(be[t + 1]); ed.push_back(ed[t + 1] + 1); } else { int t; std::cin >> t; std::cout << arrays[t + 1].get(be[t + 1]) << std::endl; arrays.push_back(arrays[t + 1].set(0, 0)); be.push_back(be[t + 1] + 1); ed.push_back(ed[t + 1]); } } }