Submission #723656

#TimeUsernameProblemLanguageResultExecution timeMemory
723656Mr_HusanboyMagic Tree (CEOI19_magictree)C++17
3 / 100
35 ms1772 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int inf = 1e9; struct Segtree{ struct node{ int mx = 0; void set(int x){ mx = max(mx, x); } node(int x){mx = x;} node(){mx = 0;}; }; node merge(node a, node b){ return node(max(a.mx, b.mx)); } vector<node> t; int n; void init(int _n){ n = _n; t.resize(4 * n, node()); } void upd(int x, int lx, int rx, int ind, int val){ if(lx == rx){ t[x].set(val); return; } int m = (lx + rx) / 2; if(ind <= m){ upd(x * 2, lx, m, ind, val); }else upd(x * 2 + 1, m + 1, rx, ind, val); t[x] = merge(t[x * 2], t[x * 2 + 1]); } node get(int x, int lx, int rx, int l, int r){ if(l <= lx && rx <= r) return t[x]; if(r < lx || rx < l){ return {0}; } int m = (lx + rx) / 2; return merge(get(x * 2, lx, m, l, r), get(x * 2 + 1, m + 1, rx, l, r)); } void upd(int ind, int val){ upd(1, 0, n - 1, ind, val); } node get(int l, int r){ return get(1, 0, n - 1, l, r); } }; void sub3(int &n, int &m, int &k, vector<int> p, vector<int> &v, vector<int> &day, vector<int> &cost){ //cout << "start" << endl; vector<int> fr(n); for(int i = 0; i < n; i ++){ fr[v[i] - 1] = day[i]; } Segtree t; t.init(k + 1); int ans = 0; for(int i = n - 1; i >= 0; i --){ int mx = t.get(0, fr[i]).mx + 1; ans = max(ans, mx); t.upd(fr[i], mx); } cout << ans; } void solve(){ int n, m, k; cin >> n >> m >> k; vector<int> p(n), v(m), day(m), cost(m); for(int i = 1; i < n; i ++){ int x; cin >> x; x --; } ll ans= 0; for(int i = 0; i < m; i ++){ cin >> v[i] >> day[i] >> cost[i]; ans += cost[i]; } cout << ans; return; sub3(n, m, k, p, v, day, cost); } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int testcases = 1; while(testcases --){ solve(); if(testcases) cout << '\n'; #ifdef LOCAL else cout << '\n'; cout << "__________________________" << endl; #endif } 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...