Submission #872084

#TimeUsernameProblemLanguageResultExecution timeMemory
872084sleepntsheepBall Machine (BOI13_ballmachine)C++17
0 / 100
18 ms8284 KiB
#include <iostream> #include <bitset> #include <cstring> #include <vector> #include <algorithm> #include <deque> #include <set> #include <utility> #include <array> using i64 = long long; using u64 = unsigned long long; using f64 = double; using f80 = long double; using namespace std; #define ALL(x) x.begin(), x.end() #define ShinLena cin.tie(nullptr)->sync_with_stdio(false); #define N 100000 int root, n, q, L[N], J[N], P[N], alloc, ta[N], h[N], tin[N], rv[N], timer, t[N<<1]; char lz[N]; struct { int v, l; } g[N-1]; inline void link(int u, int v) { if (h[u]) g[++alloc] = {v, 0}, g[ta[u]].l = alloc, ta[u] = alloc; else g[++alloc] = {v, h[u]}, h[u] = ta[u] = alloc; } inline void push(int v, int l, int r) { if (-1 == lz[v]) return; t[v] = lz[v] * (r-l+1); if (l != r) { int m = (l+r)/2, vl=v+1, vr=v+(m-l+1)*2; lz[vl] = lz[vr] = lz[v]; } lz[v] = -1; } int qry(int x, int y, int v = 0, int l = 0, int r = n - 1) { push(v, l, r); if (y < l || r < x) return 0; if (x <= l && r <= y) return t[v]; int m = (l+r)/2, vl =v + 1, vr=v+(m-l+1)*2; return qry(x, y, vl, l, m) + qry(x, y, vr, m+1, r); } int qry(int u) { return qry(tin[u], tin[u]); } void update(int x, int y, int k, int v = 0, int l = 0, int r = n - 1) { push(v, l, r); if (y < l || r < x) return; int m = (l+r)/2, vl =v + 1, vr=v+(m-l+1)*2; if (x <= l && r <= y) {lz[v] = k; push(v, l, r); return; } update(x, y, k, vl, l, m), update(x, y, k, vr, m+1, r); t[v] = t[vl]+t[vr]; } void dfs(int u) { for (auto j = h[u]; j; j = g[j].l) { P[g[j].v] = u; if (L[u] - L[J[u]] == L[J[u]] - L[J[J[u]]]) J[g[j].v] = J[J[u]]; else J[g[j].v] = u; L[g[j].v] = L[u] + 1; dfs(g[j].v); } rv[tin[u] = timer++] = u; } int highest(int u) { for (; u != P[u]; ) { if (qry(J[u])) u = J[u]; else if (qry(P[u])) u = P[u]; else break; } return u; } int main() { ShinLena; cin >> n >> q; for (int i = 0; i < n; ++i) cin >> P[i], (P[i] ? link(P[i]-1, i) : void(root = i)); P[root] = root; memset(lz, -1, sizeof lz); dfs(0); return 0; for (int t, k; q--;) { cin >> t >> k; if (t == 1) { int l = 0, r = n - 1; while (l <= r) { int m = (l+r)/2; if (qry(0, m) <= k) l = m + 1; else r = m - 1; } cout << rv[l-1] + 1 << '\n'; update(0, l-1, 1); } else { int r = highest(k-1); update(tin[r], tin[r], 0); cout << L[k-1] - L[r] << '\n'; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...