#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
#define MAX 301010
typedef long long ll;
struct node {
ll sum;
ll mx;
ll cnt;
ll mx2;
node(ll x) {
sum = mx = x;
cnt = 1;
mx2 = -1;
}
node() {
cnt = -1;
sum = 0;
mx = mx2 = 0;
}
};
node operator+(node n1, node n2) {
if (!~n1.cnt) return n2;
if (!~n2.cnt) return n1;
node ret;
ret.sum = n1.sum + n2.sum;
ret.mx = max(n1.mx, n2.mx);
ret.mx2 = max(n1.mx2, n2.mx2);
if (n1.mx != n2.mx) ret.mx2 = max(ret.mx2, min(n1.mx, n2.mx));
ret.cnt = 0;
if (ret.mx == n1.mx) ret.cnt += n1.cnt;
if (ret.mx == n2.mx) ret.cnt += n2.cnt;
return ret;
}
node tree[MAX * 4];
ll lazy[MAX * 4];
ll H[MAX];
int N;
void init(int s, int e, int loc = 1) {
lazy[loc] = 1e18;
if (s == e) {
tree[loc] = node(H[s]);
return;
}
int m = s + e >> 1;
init(s, m, loc * 2);
init(m + 1, e, loc * 2 + 1);
tree[loc] = tree[loc * 2] + tree[loc * 2 + 1];
}
void prop(int loc) {
for (auto c : { loc * 2, loc * 2 + 1 }) {
ll d = tree[c].mx - lazy[loc];
tree[c].mx = min(tree[c].mx, lazy[loc]);
if (d < 0) d = 0;
tree[c].sum -= 1ll * d * tree[c].cnt;
lazy[c] = min(lazy[c], lazy[loc]);
}
lazy[loc] = 1e18;
}
void upd(int s, int e, int i, ll x, int loc = 1) {
if (e < i || i < s) return;
if (s != e) prop(loc);
if (s == e) {
tree[loc] = node(x);
return;
}
int m = s + e >> 1;
upd(s, m, i, x, loc * 2);
upd(m + 1, e, i, x, loc * 2 + 1);
tree[loc] = tree[loc * 2] + tree[loc * 2 + 1];
}
void upd(int i, ll x) { upd(1, N, i, x); }
void down(int s, int e, int l, int r, ll x, int loc = 1) {
if (e < l || r < s) return;
if (s != e) prop(loc);
int c = 0;
if (l <= s && e <= r) {
lazy[loc] = min(lazy[loc], x);
c = 1;
if (tree[loc].mx <= x) return;
else if (tree[loc].mx2 < x) {
tree[loc].sum -= 1ll * (tree[loc].mx - x) * tree[loc].cnt;
tree[loc].mx = x;
return;
}
c = 0;
}
if (!c) {
int m = s + e >> 1;
down(s, m, l, r, x, loc * 2);
down(m + 1, e, l, r, x, loc * 2 + 1);
tree[loc] = tree[loc * 2] + tree[loc * 2 + 1];
}
}
void down(int l, int r, ll x) { down(1, N, l, r, x); }
node query(int s, int e, int l, int r, int loc = 1) {
if (e < l || r < s) return node();
if (s != e) prop(loc);
if (l <= s && e <= r) return tree[loc];
int m = s + e >> 1;
return query(s, m, l, r, loc * 2) + query(m + 1, e, l, r, loc * 2 + 1);
}
node query(int l, int r) { return query(1, N, l, r); }
int mxcount(int s, int e, int l, int r, ll x, int k, int loc = 1) {
if (e < l || r < s) return -1;
if (s != e) prop(loc);
if (l <= s && e <= r) {
if (x == tree[loc].mx) {
if (tree[loc].cnt < k) return -1;
if (s == e) return s;
int m = s + e >> 1;
if (tree[loc * 2].mx == x && tree[loc * 2].cnt >= k) return mxcount(s, m, l, r, x, k, loc * 2);
else return mxcount(m + 1, e, l, r, x, k - tree[loc * 2].cnt, loc * 2 + 1);
}
else return -1;
}
int m = s + e >> 1;
int res = mxcount(s, m, l, r, x, k, loc * 2);
if (~res) return res;
auto q = query(s, m, l, r, loc * 2);
return mxcount(m + 1, e, l, r, x, k - q.cnt, loc * 2 + 1);
}
int mxcount(int l, int r, ll x, int k) { return mxcount(1, N, l, r, x, k); }
void initialise(int N, int Q, int h[]) {
::N = N;
int i;
for (i = 1; i <= N; i++) H[i] = h[i];
init(1, N);
}
void cut(int l, int r, int k) {
while (k) {
auto res = query(l, r);
if (res.mx == 0) return;
if (res.cnt >= k) {
int ind = mxcount(l, r, res.mx, k);
assert(1 <= ind);
down(l, ind, res.mx - 1);
break;
}
ll rem = res.mx - max(0ll, res.mx2);
rem *= res.cnt;
ll m = min(k / res.cnt, res.mx - res.mx2);
down(l, r, res.mx - m);
k -= m * res.cnt;
}
}
void magic(int i, int x) { upd(i, x); }
long long int inspect(int l, int r) { return query(l, r).sum; }
Compilation message
weirdtree.cpp: In function 'void init(int, int, int)':
weirdtree.cpp:49:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
49 | int m = s + e >> 1;
| ~~^~~
weirdtree.cpp: In function 'void upd(int, int, int, ll, int)':
weirdtree.cpp:73:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
73 | int m = s + e >> 1;
| ~~^~~
weirdtree.cpp: In function 'void down(int, int, int, int, ll, int)':
weirdtree.cpp:96:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
96 | int m = s + e >> 1;
| ~~^~~
weirdtree.cpp: In function 'node query(int, int, int, int, int)':
weirdtree.cpp:108:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
108 | int m = s + e >> 1;
| ~~^~~
weirdtree.cpp: In function 'int mxcount(int, int, int, int, ll, int, int)':
weirdtree.cpp:120:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
120 | int m = s + e >> 1;
| ~~^~~
weirdtree.cpp:126:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
126 | int m = s + e >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
47 ms |
77008 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
47 ms |
77008 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
45 ms |
77004 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
45 ms |
77004 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
218 ms |
51148 KB |
Output is correct |
| 2 |
Correct |
231 ms |
51292 KB |
Output is correct |
| 3 |
Correct |
39 ms |
41188 KB |
Output is correct |
| 4 |
Correct |
76 ms |
41044 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
47 ms |
77008 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
47 ms |
77008 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
