#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct node {
ll max, freqmax, smax, sum;
};
ll t[300005];
node combine(node a, node b) {
if (a.max < b.max) {
swap(a, b);
}
if (a.max > b.max) {
return {a.max, a.freqmax, max(a.smax, b.max), a.sum + b.sum};
} else {
return {a.max, a.freqmax + b.freqmax, max(a.smax, b.smax), a.sum + b.sum};
}
}
node tree[300005 * 4];
ll cutoff[300005 * 4];
bool isleaf[300005];
void pushdown(ll x) {
// // // cout << x << " " << l << " " << r << " " << cutoff[x] << " " << tree[x].max;
if (cutoff[x] >= tree[x].max) {
cutoff[x] = 1e10;
return;
}
if (isleaf[x]) {
tree[x] = {cutoff[x], 1, 0, cutoff[x]};
cutoff[x] = 1e10;
return;
}
if (cutoff[x] > tree[x].smax) {
tree[x].sum += (ll) (tree[x].freqmax * (cutoff[x] - tree[x].max));
tree[x].max = cutoff[x];
}
cutoff[2 * x] = min(cutoff[2 * x], cutoff[x]);
cutoff[ 2 * x + 1] = min(cutoff[ 2 * x + 1], cutoff[x]);
cutoff[x] = 1e10;
}
void build(ll x, ll l, ll r) {
cutoff[x] = 1e10;
if (l == r) {
tree[x] = {t[l], 1, 0, t[l]};
isleaf[x] = true;
return;
}
ll mid = (l + r) /2;
build(2 * x, l, mid); build(2 * x + 1, mid + 1, r);
tree[x] = combine(tree[2 * x], tree[2 * x + 1]);
}
ll n;
void initialise(int N, int q, int h[]) {
for (ll i = 1; i <= N; i++) {
t[i] = h[i];
// // // cout << t[i] << " asd " << endl;
}
n = N;
// // cout << "llialise " << endl;
build(1, 1, n);
}
node getNode(int x, int l, int r, int ql, int qr) {
pushdown(x);
if (ql <= l && r <= qr) return tree[x];
int mid =(l +r) / 2;
if (qr <= mid) return getNode(2 * x, l, mid, ql, qr);
else if (ql > mid) return getNode(2 * x + 1, mid + 1, r, ql, qr);
return combine(getNode(2 * x, l, mid, ql, qr), getNode(2 * x + 1, mid + 1, r, ql, qr));
}
void lazy(ll x, ll l, ll r, ll ql, ll qr, ll lazyval) {
pushdown(x);
if (ql > r || qr < l || l > r || lazyval > tree[x].max) return;
if ((ql <= l && r <= qr && lazyval > tree[x].smax) || (l == r)) {
cutoff[x] = lazyval;
pushdown(x);
return;
}
# warning may need to fix
ll mid = (l + r) / 2;
lazy(2 * x, l, mid, ql, qr, lazyval);
lazy(2 * x + 1, mid + 1, r, ql, qr, lazyval);
tree[x] = combine(tree[2 * x], tree[2 * x + 1]);
}
ll walkdown(ll x, ll l, ll r, ll ql, ll qr, ll &ct, ll maxcomp) {
pushdown(x);
if (tree[x].max < maxcomp || l > qr || r < ql) return 0;
if (ql <= l && r <= qr && tree[x].freqmax < ct) {
ct -= tree[x].freqmax;
return 0;
}
if (l == r) {
ct--;
return l;
}
ll mid = (l + r) / 2;
ll nextidx = walkdown(2 * x, l, mid, ql, qr, ct, maxcomp);
if (nextidx) return nextidx;
return walkdown(2 * x + 1, mid + 1, r, ql, qr, ct, maxcomp);
}
void cut(int l, int r, int k) {
while (k > 0) {
auto asd = getNode(1, 1, n, l, r);
if (asd.max == 0) return;
ll curavail = (asd.max - asd.smax) * asd.freqmax;
if (curavail <= k) {
lazy(1, 1, n, l, r, asd.smax);
k -= curavail;
continue;
}
ll m = k % asd.freqmax;
ll newval = asd.max - k / asd.freqmax;
if (m == 0) {
lazy(1, 1, n, l, r, newval);
} else {
ll idx = walkdown(1, 1, n, l, r, m, asd.max);
lazy(1, 1, n, l, idx, newval- 1);
lazy(1, 1, n, idx + 1, r, newval);
}
break;
}
return;
}
void setbruh(ll x, ll l, ll r, ll i, ll xx) {
pushdown(x);
if (l == r) {
tree[x] = {xx, 1, 0, xx};
return;
}
ll mid = (l + r) / 2;
if (i <= mid) setbruh(2 * x, l, mid, i, xx);
else setbruh(2 * x + 1, mid + 1, r, i, xx);
pushdown(2 * x);
pushdown(2 * x + 1);
tree[x] = combine(tree[2 * x], tree[2 * x + 1]);
}
void magic(int i, int x ) {
// // cout << "magic " << endl;
setbruh(1, 1, n, i, x);
}
ll getSum(int x, int l, int r, int ql, int qr) {
pushdown(x);
if (l > qr || r < ql) return 0;
if (l <= ql && qr <= r) return tree[x].sum;
int mid = (l + r) / 2;
ll a = getSum(2 * x , l, mid, ql, qr);
ll b = getSum(2 * x + 1, mid + 1, r, ql, qr);
tree[x] = combine(tree[2 * x], tree[2 * x + 1]);
return a + b;
}
ll inspect(int l, int r) {
// // cout << "inspect " << endl;
return getSum(1, 1, n, l, r);
}
Compilation message
weirdtree.cpp:129:3: warning: #warning may need to fix [-Wcpp]
129 | # warning may need to fix
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
181 ms |
46716 KB |
Output is correct |
| 2 |
Incorrect |
235 ms |
46896 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
