Submission #674237

#TimeUsernameProblemLanguageResultExecution timeMemory
674237tibinyteConstellation 3 (JOI20_constellation3)C++17
100 / 100
740 ms153648 KiB
#include <bits/stdc++.h> #define int long long using namespace std; struct bit { vector<int> b; void resize(int n) { b = vector<int>(n + 2); } void update(int pos, int val) { int n = (int)b.size() - 1; for (int i = pos; i <= n; i += i & (-i)) { b[i] += val; } } int query(int pos) { int ans = 0; for (int i = pos; i; i -= i & (-i)) { ans += b[i]; } return ans; } void update(int st, int dr, int val) { update(st, val); update(dr + 1, -val); } }; struct rmq { vector<vector<pair<int, int>>> rmq; vector<int> lg; void build(vector<int> a, int n) { lg = vector<int>(n + 1); for (int i = 2; i <= n; ++i) { lg[i] = lg[i / 2] + 1; } rmq = vector<vector<pair<int, int>>>(n + 1, vector<pair<int, int>>(lg[n] + 1)); for (int i = 1; i <= n; ++i) { rmq[i][0] = {a[i], i}; } for (int j = 1; j <= lg[n]; ++j) { for (int i = 1; i + (1 << j) - 1 <= n; ++i) { rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]); } } } pair<int, int> query(int st, int dr) { int pow_2 = lg[dr - st + 1]; return min(rmq[st][pow_2], rmq[dr - (1 << pow_2) + 1][pow_2]); } }; struct cartesian { vector<int> a; vector<vector<int>> g; vector<vector<pair<int, int>>> stars; vector<vector<int>> jump; vector<int> tin; vector<int> tout; vector<int> dp; int p = 0; int root; int max_jump; int n; void build(vector<int> _a, int _n) { n = _n; a = _a; dp = tin = tout = vector<int>(n + 1); g = vector<vector<int>>(n + 1); rmq t; t.build(a, n); max_jump = t.lg[n]; jump = vector<vector<int>>(n + 1, vector<int>(max_jump + 1)); stars = vector<vector<pair<int, int>>>(n + 1); function<void(int, int, int)> construct = [&](int st, int dr, int parent) { pair<int, int> qui = t.query(st, dr); if (parent != 0) { g[parent].push_back(qui.second); g[qui.second].push_back(parent); jump[qui.second][0] = parent; } else { jump[qui.second][0] = qui.second; root = qui.second; } for (int i = 1; i <= max_jump; ++i) { jump[qui.second][i] = jump[jump[qui.second][i - 1]][i - 1]; } tin[qui.second] = ++p; if (qui.second != st) { construct(st, qui.second - 1, qui.second); } if (qui.second != dr) { construct(qui.second + 1, dr, qui.second); } tout[qui.second] = ++p; }; construct(1, n, 0); } void insert(int node, int h, int coef) { int qui = node; for (int i = max_jump; i >= 0; --i) { if (a[jump[node][i]] >= h) { node = jump[node][i]; } } stars[node].push_back({qui, coef}); } int solve() { bit tree; bit tree2; tree.resize(p); tree2.resize(p); function<void(int, int)> dfs = [&](int node, int parent) { for (auto i : g[node]) { if (i != parent) { dfs(i, node); } } int sum = 0; for (auto i : g[node]) { if (i != parent) { sum += dp[i]; } } tree.update(tin[node], tout[node], sum); dp[node] = sum; for (auto chain : stars[node]) { dp[node] = max(dp[node], chain.second + tree.query(tin[chain.first]) - tree2.query(tin[chain.first])); } tree2.update(tin[node], tout[node], dp[node]); }; dfs(root, 0); return dp[root]; } }; int32_t main() { cin.tie(nullptr)->sync_with_stdio(false); int n; cin >> n; vector<int> a(n + 1); for (int i = 1; i <= n; ++i) { cin >> a[i]; a[i] = n - a[i]; } cartesian t; t.build(a, n); int m; cin >> m; int sum = 0; for (int i = 1; i <= m; ++i) { int qui, wh, coef; cin >> qui >> wh >> coef; wh = n - wh + 1; sum += coef; t.insert(qui, wh, coef); } cout << sum - t.solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...