Submit Info #15726

Problem Lang User Status Time Memory
Persistent Queue cpp AlphaQ AC 134 ms 12.95 MiB

ケース詳細
Name Status Time Memory
ephemeral_00 AC 95 ms 9.67 MiB
example_00 AC 2 ms 0.68 MiB
half_rot_killer_00 AC 129 ms 12.95 MiB
random_00 AC 106 ms 9.66 MiB
random_01 AC 127 ms 11.42 MiB
random_02 AC 15 ms 1.90 MiB
random_2_00 AC 109 ms 9.17 MiB
random_2_01 AC 132 ms 10.82 MiB
random_2_02 AC 13 ms 1.80 MiB
random_3_00 AC 99 ms 9.20 MiB
random_3_01 AC 111 ms 10.79 MiB
random_3_02 AC 15 ms 1.80 MiB
two_stacks_killer_00 AC 134 ms 11.76 MiB

#include <bits/stdc++.h> using namespace std; const int N = 500010; int q, p[N], h[N], jump[N], sz[N], val[N]; int get (int x, int d) { while (h[x] > d) { x = h[jump[x]] < d ? p[x] : jump[x]; } return x; } int main() { cin >> q; p[0] = -1; for (int i = 1; i <= q; ++i) { int cmd, t, v; scanf("%d %d", &cmd, &t); ++t; if (cmd) { val[i] = val[t], p[i] = p[t], h[i] = h[t], sz[i] = sz[t] - 1, jump[i] = jump[t]; printf("%d\n", val[get(t, h[t] - sz[t] + 1)]); } else { scanf("%d", &v); val[i] = v, p[i] = t, h[i] = h[t] + 1, sz[i] = sz[t] + 1; int x = jump[t], y = jump[x]; jump[i] = (h[t] + h[y] == h[x] << 1) ? y : t; } } return 0; }