Submission #1035373

#TimeUsernameProblemLanguageResultExecution timeMemory
1035373andrei_c1Weirdtree (RMI21_weirdtree)C++17
100 / 100
1048 ms40628 KiB
#include "weirdtree.h" #include <bits/stdc++.h> using namespace std; using ll = long long; const int kInf = 1e9; void maxSelf(int &x, int y) { if(y > x) { x = y; } } struct node_t { ll sum; int mx1, mx2, frq; node_t() : sum(0), mx1(0), mx2(0), frq(0) {} node_t(int val) : sum(val), mx1(val), mx2(0), frq(1) {} node_t operator + (const node_t &oth) const { node_t res; res.sum = sum + oth.sum; if(mx1 > oth.mx1) { res.mx1 = mx1; res.mx2 = max(mx2, oth.mx1); res.frq = frq; } else if(mx1 < oth.mx1) { res.mx1 = oth.mx1; res.mx2 = max(mx1, oth.mx2); res.frq = oth.frq; } else { res.mx1 = mx1; res.mx2 = max(mx2, oth.mx2); res.frq = frq + oth.frq; } return res; } void update(int val) { sum += (ll)(val - mx1) * frq; mx1 = val; } }; vector<int> a; struct aint { int n; vector<node_t> tree; aint() {} aint(int n) : n(n), tree(n << 2 | 1) {} void build(int node, int l, int r) { if(l == r) { tree[node] = node_t(a[l]); } else { int mid = (l + r) >> 1; build(node << 1, l, mid); build(node << 1 | 1, mid + 1, r); tree[node] = tree[node << 1] + tree[node << 1 | 1]; } } void build() { build(1, 1, n); } void push(int node) { for(const auto &it : {node << 1, node << 1 | 1}) if(it <= 4 * n) { if(tree[node].mx1 < tree[it].mx1) { tree[it].update(tree[node].mx1); } } } void update(int a, int b, int val, int node, int l, int r) { if(tree[node].mx1 <= val) { return; } if(a <= l && r <= b && tree[node].mx2 < val) { tree[node].update(val); } else { push(node); int mid = (l + r) >> 1; if(a <= mid) { update(a, b, val, node << 1, l, mid); } if(b > mid) { update(a, b, val, node << 1 | 1, mid + 1, r); } tree[node] = tree[node << 1] + tree[node << 1 | 1]; } } void update(int a, int b, int val) { update(a, b, val, 1, 1, n); } void update(int p, int val, int node, int l, int r) { if(l == r) { tree[node] = node_t(val); } else { push(node); int mid = (l + r) >> 1; if(p <= mid) { update(p, val, node << 1, l, mid); } else { update(p, val, node << 1 | 1, mid + 1, r); } tree[node] = tree[node << 1] + tree[node << 1 | 1]; } } void update(int p, int val) { update(p, val, 1, 1, n); } node_t query(int a, int b, int node, int l, int r) { if(a <= l && r <= b) { return tree[node]; } else { push(node); int mid = (l + r) >> 1; node_t lhs, rhs; if(a <= mid) { lhs = query(a, b, node << 1, l, mid); } if(b > mid) { rhs = query(a, b, node << 1 | 1, mid + 1, r); } return lhs + rhs; } } node_t query(int a, int b) { return query(a, b, 1, 1, n); } } ds; void initialise(int n, int q, int h[]) { a = vector<int>(n + 1); for(int i = 1; i <= n; i++) { a[i] = h[i]; } ds = aint(n); ds.build(); } void cut(int ql, int qr, int k) { while(k > 0) { node_t ans = ds.query(ql, qr); if(ans.mx1 == 0) { return; } ll cuts = (ll)(ans.mx1 - ans.mx2) * ans.frq; if(cuts <= k) { ds.update(ql, qr, ans.mx2); k -= cuts; } else { int extra = k % ans.frq, l = ql, r = qr, mid; while(l <= r) { mid = (l + r) >> 1; node_t res = ds.query(ql, mid); if(res.mx1 < ans.mx1 || (res.mx1 == ans.mx1 && res.frq <= extra)) { l = mid + 1; } else { r = mid - 1; } } ds.update(ql, qr, ans.mx1 - k / ans.frq); if(ql <= l - 1) { ds.update(ql, l - 1, ans.mx1 - 1 - k / ans.frq); } k = 0; } } } void magic(int i, int x) { ds.update(i, x); } ll inspect(int l, int r) { return ds.query(l, r).sum; }
#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...