Submission #372278

#TimeUsernameProblemLanguageResultExecution timeMemory
372278gustasonAirplanes (LMIO17_lektuvai)C++11
11 / 100
62 ms6636 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; struct Node { int mx; int setAll; bool setAllValid; Node() { setAllValid = false; setAll = 0; mx = 0; } void Reset() { setAllValid = false; } }; struct SegTree { int n; vector<Node> tree; SegTree(vector<int>& a) { n = a.size(); tree.assign(4*n, Node()); build_r(a, 0, n-1, 0); } void build_r(vector<int>& a, int l, int r, int idx) { if (l == r) { if (l < n) tree[idx].mx = a[l]; else tree[idx].mx = 0; return; } int mid = (l + r) / 2; build_r(a, l, mid, 2*idx+1); build_r(a, mid+1, r, 2*idx+2); tree[idx].mx = max(tree[2*idx+1].mx, tree[2*idx+2].mx); } void applyAggr(int idx, int l, int r) { if (tree[idx].setAllValid) tree[idx].mx = max(tree[idx].mx, tree[idx].setAll); if (l != r) { compose(idx, 2*idx+1); compose(idx, 2*idx+2); } tree[idx].Reset(); } void compose(int par, int child) { if (tree[par].setAllValid) { tree[child].setAllValid = true; tree[child].setAll = tree[par].setAll; } } void updateSet(int L, int R, int val) { updateSet_r(0, 0, n-1, L, R, val); } void updateSet_r(int idx, int l, int r, int& L, int& R, int& val) { if (r < L || R < l || l >= n) return; if (L <= l && R >= r) { tree[idx].setAllValid = true; tree[idx].setAll = val; return; } applyAggr(idx, l, r); int mid = (l + r) / 2; updateSet_r(2*idx+1, l, mid, L, R, val); updateSet_r(2*idx+2, mid+1, r, L, R, val); applyAggr(2*idx+1, l, mid); applyAggr(2*idx+2, mid+1, r); tree[idx].mx = max(tree[2*idx+1].mx, tree[2*idx+2].mx); } int getMax(int L, int R) { return getMax_r(0, 0, n-1, L, R); } int getMax_r(int idx, int l, int r, int& L, int& R) { if (r < L || R < l || l >= n) return 0; applyAggr(idx, l, r); if (L <= l && R >= r) return tree[idx].mx; int mid = (l + r) / 2; return max(getMax_r(2*idx+1, l, mid, L, R), getMax_r(2*idx+2, mid+1, r, L, R)); } }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n); for(int i = 0; i < n; i++) { cin >> a[i]; } vector<int> p(n); p[n-1] = -1; for(int i = 0; i < n-1; i++) { cin >> p[i]; p[i]--; } if (n <= 1000) { int q; cin >> q; for(int i = 0; i < q; i++) { char type; cin >> type; if (type == 'I') { int idx; cin >> idx; idx--; cout << a[idx] << "\n"; } else if (type == 'P') { int idx, by; cin >> idx >> by; idx--; a[idx] += by; vector<bool> vis(n+1, false); while(1) { int par = p[idx]; if (par == -1 || vis[par]) break; a[par] = max(a[par], a[idx]); idx = par; } } } } else { int q; cin >> q; SegTree tree(a); for(int i = 0; i < q; i++) { char type; cin >> type; if (type == 'I') { int idx; cin >> idx; idx--; cout << tree.getMax(0, idx) << "\n"; } else if (type == 'P') { int idx, by; cin >> idx >> by; idx--; a[idx] = tree.getMax(0, idx) + by; tree.updateSet(idx, n-1, a[idx]); } } } // vector<int> a(4); // a = {2, 4, 5, 5}; // SegTree tree(a); // tree.updateSet(0, 2, 8); // tree.updateSet(0, 3, 6); // tree.updateSet(0, 3, 4); // tree.updateSet(0, 3, 7); // tree.updateSet(0, 1, 9); // for(int i = 0; i < 4; i++) { // cout << tree.getMax(i, i) << " "; // } cout << "\n"; // cout << tree.getMax(2, 3) << "\n"; 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...