제출 #971430

#제출 시각아이디문제언어결과실행 시간메모리
971430Pannda밀림 점프 (APIO21_jumps)C++17
4 / 100
900 ms77608 KiB
#include "jumps.h" #include <bits/stdc++.h> using namespace std; struct SegmentTree { struct Node { int sum = 0; int ln = 0, rn = 0; }; int n; vector<Node> nodes; vector<int> roots; SegmentTree() {} SegmentTree(int n) : n(n), nodes(1), roots(1, 0) {} void add(int i, int delta, int base, int &idx, int l, int r) { idx = nodes.size(); nodes.push_back(nodes[base]); nodes[idx].sum += delta; if (l + 1 < r) { int m = (l + r) >> 1; Node goat = nodes[idx]; if (i < m) add(i, delta, nodes[base].ln, goat.ln, l, m); else add(i, delta, nodes[base].rn, goat.rn, m, r); nodes[idx] = goat; } } void add(int i, int val) { roots.emplace_back(); add(i, val, roots.end()[-2], roots.end()[-1], 0, n); } int find(int ub, int idxl, int idxr) { auto dfs = [&](auto self, int idxl, int idxr, int l, int r) -> int { if (l >= ub) return -1; if (nodes[idxr].sum - nodes[idxl].sum == 0) return -1; if (l + 1 == r) return l; int m = (l + r) >> 1; int get = self(self, nodes[idxl].rn, nodes[idxr].rn, m, r); if (get != -1) return get; return self(self, nodes[idxl].ln, nodes[idxr].ln, l, m); }; return dfs(dfs, idxl, idxr, 0, n); } }; const int LOG = 17; int n; vector<int> h, ih; vector<vector<int>> f; vector<int> depth; SegmentTree seg; void init(int N, vector<int> H) { n = N; h = H; ih = vector<int>(n); for (int i = 0; i < n; i++) { h[i]--; ih[h[i]] = i; } h.push_back(n); f = vector<vector<int>>(n + 1, vector<int>(LOG, n)); depth = vector<int>(n + 1, 0); vector<int> stk = { n }; for (int i = n - 1; i >= 0; i--) { while (h[stk.back()] < h[i]) stk.pop_back(); depth[i] = depth[stk.back()] + 1; f[i][0] = stk.back(); stk.push_back(i); } stk.clear(); for (int i = 0; i < n; i++) { while (!stk.empty() && h[stk.back()] < h[i]) stk.pop_back(); if (!stk.empty() && depth[stk.back()] < depth[f[i][0]]) { f[i][0] = stk.back(); } stk.push_back(i); } for (int k = 1; k < LOG; k++) { for (int i = 0; i < n; i++) { f[i][k] = f[f[i][k - 1]][k - 1]; } } seg = SegmentTree(n + 1); for (int i = 0; i < n; i++) { seg.add(h[i], +1); } } int minimum_jumps(int l0, int r0, int l1, int r1) { r0++; r1++; int res = n; for (int to = l1; to < r1; to++) { int from = seg.find(h[to], seg.roots[l0], seg.roots[r0]); if (from == -1) continue; from = ih[from]; int cnt = 0; for (int k = LOG - 1; k >= 0; k--) { int next = f[from][k]; if (depth[next] >= depth[to]) { from = next; cnt += 1 << k; } } res = min(res, cnt + depth[from] - depth[to]); break; } if (res == n) return -1; return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...