Submit Info #30162

Problem Lang User Status Time Memory
Persistent Queue cpp hitonanode AC 263 ms 40.46 MiB

ケース詳細
Name Status Time Memory
ephemeral_00 AC 129 ms 26.46 MiB
example_00 AC 3 ms 0.67 MiB
half_rot_killer_00 AC 153 ms 28.71 MiB
random_00 AC 160 ms 27.96 MiB
random_01 AC 188 ms 32.96 MiB
random_02 AC 18 ms 4.35 MiB
random_2_00 AC 213 ms 38.69 MiB
random_2_01 AC 263 ms 39.19 MiB
random_2_02 AC 21 ms 5.40 MiB
random_3_00 AC 148 ms 38.64 MiB
random_3_01 AC 170 ms 38.93 MiB
random_3_02 AC 20 ms 5.48 MiB
two_stacks_killer_00 AC 181 ms 40.46 MiB

#pragma once #include <array> #include <cassert> #include <utility> #include <vector> // CUT begin // Fully persistent queue template <typename T, int D> struct persistent_queue { int now; std::vector<T> data; // Elements on each node of tree std::vector<std::vector<int>> par; // binary-lifted parents std::vector<int> back_id; // back_id[t] = leaf id of the tree at time t std::vector<int> size; // size[t] = size of the queue at time t persistent_queue() : now(0), data(1), par(1, std::vector<int>(D)), back_id(1, 0), size(1, 0) {} // Complexity: O(lgD) // return: (curret_time, popped element) std::pair<int, T> pop(int t) { now++; assert(now < 1 << (D + 1)); int r = back_id[t], len = size[t] - 1; back_id.emplace_back(r), size.emplace_back(len); for (int d = 0; d < D; d++) if ((len >> d) & 1) r = par[r][d]; return std::make_pair(now, data[r]); } // Complexity: O(lgD) // return: curret_time int push(int t, const T &dat) { now++; assert(now < 1 << (D + 1)); int newid = data.size(); data.emplace_back(dat); par.emplace_back(std::vector<int>(D, back_id[t])); back_id.emplace_back(newid), size.emplace_back(size[t] + 1); for (int d = 1; d < D; d++) par[newid][d] = par[par[newid][d - 1]][d - 1]; return now; } }; #include <iostream> #define PROBLEM "https://judge.yosupo.jp/problem/persistent_queue" using namespace std; int main() { cin.tie(nullptr), ios::sync_with_stdio(false); persistent_queue<int, 18> pq; int Q; cin >> Q; while (Q--) { int q, t; cin >> q >> t; if (q == 0) { int x; cin >> x; pq.push(t + 1, x); } else { cout << pq.pop(t + 1).second << '\n'; } } }