Submission #770196

#TimeUsernameProblemLanguageResultExecution timeMemory
770196PurpleCrayonConstellation 3 (JOI20_constellation3)C++17
35 / 100
1582 ms53624 KiB
#include <bits/stdc++.h> using namespace std; #define sz(v) int(v.size()) #define ar array typedef long long ll; const int N = 2e5+10, MOD = 998244353; const int L = 18; struct FT { vector<ll> bit; FT() {} FT(int n) { bit.resize(n); } void upd(int i, int x) { for (; i < sz(bit); i |= i+1) bit[i] += x; } ll qry(int i) { ll ans = 0; for (++i; i > 0; i &= i-1) ans += bit[i-1]; return ans; } } bit; int n, m, a[N], st[N], en[N], bro[N], anc[N][L]; int par[N]; vector<int> child[N]; vector<pair<int, ll>> can[N]; ll dp[N]; int tt = 0; void dfs_st(int c) { st[c] = tt++; for (int nxt : child[c]) { dfs_st(nxt); } en[c] = tt-1; } void build_tree() { memset(par, -1, sizeof(par)); vector<int> st; for (int i = 0; i < n; i++) { int last = -1; while (sz(st) && a[st.back()] < a[i]) { last = st.back(); st.pop_back(); } if (sz(st)) par[i] = st.back(); if (last != -1) par[last] = i; st.push_back(i); } } ll f(int bot, int top) { // return bit.qry(st[bot]) - bit.qry(st[top]); if (bot == top) return 0; return dp[bro[bot]] + f(par[bot], top); } void dfs(int c) { for (int nxt : child[c]) { dfs(nxt); } for (int nxt : child[c]) { bit.upd(st[nxt], dp[bro[nxt]]); bit.upd(en[nxt]+1, -dp[bro[nxt]]); } dp[c] = 0; for (int nxt : child[c]) dp[c] += dp[nxt]; for (auto [v, x] : can[c]) { ll cur = x + f(v, c); for (int nxt : child[v]) cur += dp[nxt]; dp[c] = max(dp[c], cur); } } void solve() { cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; bit = FT(n); build_tree(); int root = -1; for (int i = 0; i < n; i++) { if (par[i] == -1) { root = i; } } for (int i = 0; i < n; i++) if (i != root) { child[par[i]].push_back(i); } memset(bro, -1, sizeof(bro)); for (int i = 0; i < n; i++) if (i != root) { for (int nxt : child[par[i]]) if (nxt != i) { bro[i] = nxt; } } dfs_st(root); for (int i = 0; i < n; i++) { anc[i][0] = par[i]; } for (int k = 1; k < L; k++) { for (int i = 0; i < n; i++) { anc[i][k] = anc[i][k-1] == -1 ? -1 : anc[anc[i][k-1]][k-1]; } } cin >> m; ll base = 0; for (int i = 0; i < m; i++) { int x, y; ll c; cin >> x >> y >> c, --x; base += c; int top = x; for (int k = L-1; k >= 0; k--) { if (anc[top][k] != -1 && a[anc[top][k]] < y) { top = anc[top][k]; } } can[top].push_back({x, c}); } dfs(root); cout << base - dp[root] << '\n'; } int main() { ios::sync_with_stdio(false); cin.tie(0); int T = 1; // cin >> T; while (T--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...