Super Mario 2 solution
unknown
c_cpp
5 months ago
1.9 kB
4
Indexable
#include<bits/stdc++.h> #define int long long using namespace std; class segtree { private: vector<int> a,t; int n; void build(int l, int r, int node){ //O(n) int mid = (l + r) / 2; if (l == r) t[node] = a[l]; else { build(l, mid, node * 2+1); build(mid + 1, r, node * 2 + 2); t[node] = min(t[node * 2 + 1], t[node * 2 + 2]); } } int rmq(int l, int r, int i, int j, int node) { int mid = (l + r) / 2; if (i <= l && j >= r) return t[node]; if (j < l || r < i) return 1e17; int p1 = rmq(l, mid, i, j, node * 2 + 1); int p2 = rmq(mid + 1, r, i, j, node * 2 + 2); return min(p1, p2); } void update(int l, int r, int idx, int val, int node) { int mid = (l + r) / 2; if (idx < l || r < idx) return; else if (l == r) t[node] = val; else { update(l, mid, idx, val, node * 2 + 1); update(mid + 1, r, idx,val, node * 2 + 2); t[node] = min(t[node * 2 + 1], t[node * 2 + 2]); } } public: segtree(int n, vector<int>& arr) { this->n = n; t.resize(4 * n), a.resize(n); for (int i = 0; i < n; ++i) a[i] = arr[i]; build(0, n - 1, 0); } void update(int idx, int val) { update(0, n - 1, idx, val, 0); } int rmq(int l, int r) { return rmq(0, n - 1, l, r, 0); } }; int32_t main() { int n; cin >> n; vector<int> a(n + 1), c(n + 1), dp(n + 1, 1e17); for(int i = 1; i <= n;++i) cin >> c[i]; for(int i = 1; i <= n;++i) cin >> a[i]; dp[n] = 0; segtree tree(n + 1, dp); for(int i = n - 1; i >= 1; --i) dp[i] = tree.rmq(i + 1, a[i]) + c[i], tree.update(i, dp[i]); cout << dp[1]; }
Editor is loading...
Leave a Comment