#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() {}
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;
}
Compilation message
weirdtree.cpp: In member function 'node_t aint::query(int, int, int, int, int)':
weirdtree.cpp:29:12: warning: 'rhs.node_t::frq' may be used uninitialized in this function [-Wmaybe-uninitialized]
29 | res.frq = oth.frq;
| ~~~~~~~~^~~~~~~~~
weirdtree.cpp:114:16: note: 'rhs.node_t::frq' was declared here
114 | node_t lhs, rhs;
| ^~~
weirdtree.cpp:114:16: warning: '*((void*)& rhs +12)' may be used uninitialized in this function [-Wmaybe-uninitialized]
weirdtree.cpp:114:16: warning: 'rhs.node_t::mx1' may be used uninitialized in this function [-Wmaybe-uninitialized]
weirdtree.cpp:21:17: warning: 'rhs.node_t::sum' may be used uninitialized in this function [-Wmaybe-uninitialized]
21 | res.sum = sum + oth.sum;
| ~~~~^~~~~~~~~
weirdtree.cpp:114:16: note: 'rhs.node_t::sum' was declared here
114 | node_t lhs, rhs;
| ^~~
weirdtree.cpp:25:12: warning: 'lhs.node_t::frq' may be used uninitialized in this function [-Wmaybe-uninitialized]
25 | res.frq = frq;
| ~~~~~~~~^~~~~
weirdtree.cpp:114:11: note: 'lhs.node_t::frq' was declared here
114 | node_t lhs, rhs;
| ^~~
weirdtree.cpp:114:11: warning: '*((void*)& lhs +12)' may be used uninitialized in this function [-Wmaybe-uninitialized]
weirdtree.cpp:26:10: warning: 'lhs.node_t::mx1' may be used uninitialized in this function [-Wmaybe-uninitialized]
26 | } else if(mx1 < oth.mx1) {
| ^~
weirdtree.cpp:114:11: note: 'lhs.node_t::mx1' was declared here
114 | node_t lhs, rhs;
| ^~~
weirdtree.cpp:21:17: warning: 'lhs.node_t::sum' may be used uninitialized in this function [-Wmaybe-uninitialized]
21 | res.sum = sum + oth.sum;
| ~~~~^~~~~~~~~
weirdtree.cpp:114:11: note: 'lhs.node_t::sum' was declared here
114 | node_t lhs, rhs;
| ^~~
weirdtree.cpp: In function 'void cut(int, int, int)':
weirdtree.cpp:33:18: warning: 'rhs.node_t::frq' may be used uninitialized in this function [-Wmaybe-uninitialized]
33 | res.frq = frq + oth.frq;
| ~~~~^~~~~~~~~
weirdtree.cpp:114:16: note: 'rhs.node_t::frq' was declared here
114 | node_t lhs, rhs;
| ^~~
weirdtree.cpp:114:16: warning: '*((void*)& rhs +12)' may be used uninitialized in this function [-Wmaybe-uninitialized]
weirdtree.cpp:26:10: warning: 'rhs.node_t::mx1' may be used uninitialized in this function [-Wmaybe-uninitialized]
26 | } else if(mx1 < oth.mx1) {
| ^~
weirdtree.cpp:114:16: note: 'rhs.node_t::mx1' was declared here
114 | node_t lhs, rhs;
| ^~~
weirdtree.cpp:33:18: warning: 'lhs.node_t::frq' may be used uninitialized in this function [-Wmaybe-uninitialized]
33 | res.frq = frq + oth.frq;
| ~~~~^~~~~~~~~
weirdtree.cpp:114:11: note: 'lhs.node_t::frq' was declared here
114 | node_t lhs, rhs;
| ^~~
weirdtree.cpp:114:11: warning: '*((void*)& lhs +12)' may be used uninitialized in this function [-Wmaybe-uninitialized]
weirdtree.cpp:114:11: warning: 'lhs.node_t::mx1' may be used uninitialized in this function [-Wmaybe-uninitialized]
weirdtree.cpp: In function 'll inspect(int, int)':
weirdtree.cpp:21:17: warning: 'rhs.node_t::sum' may be used uninitialized in this function [-Wmaybe-uninitialized]
21 | res.sum = sum + oth.sum;
| ~~~~^~~~~~~~~
weirdtree.cpp:114:16: note: 'rhs.node_t::sum' was declared here
114 | node_t lhs, rhs;
| ^~~
weirdtree.cpp:21:17: warning: 'lhs.node_t::sum' may be used uninitialized in this function [-Wmaybe-uninitialized]
21 | res.sum = sum + oth.sum;
| ~~~~^~~~~~~~~
weirdtree.cpp:114:11: note: 'lhs.node_t::sum' was declared here
114 | node_t lhs, rhs;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2066 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2066 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2024 ms |
344 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2024 ms |
344 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
341 ms |
28756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2066 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2066 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
