#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct node {
ll max, smax, freqmax; ll sum;
};
ll t[300005];
node combine(node a, node b) {
if (a.max == b.max) {
return {a.max, max(a.smax, b.smax), a.freqmax + b.freqmax, a.sum + b.sum};
}
if (a.max < b.max) {
return {b.max, max(a.max, b.smax), b.freqmax, a.sum + b.sum};
} else {
return {a.max, max(a.smax, b.max), a.freqmax, a.sum + b.sum};
}
}
node tree[300005 * 4];
ll cutoff[300005 * 4];
void reset(ll x) {
cutoff[x] = 1e15;
}
void pushdown(ll x, ll l, ll r) {
// // // cout << x << " " << l << " " << r << " " << cutoff[x] << " " << tree[x].max;
if (cutoff[x] >= tree[x].max) {
reset(x);
return;
}
if (l == r) {
tree[x] = {cutoff[x], 0, 1, cutoff[x]};
reset(x);
return;
}
if (cutoff[x] > tree[x].smax) {
// // cout << tree[x].freqmax << " " << tree[x].max << " " << cutoff[x] << endl;
tree[x].sum -= (tree[x].freqmax * (tree[x].max - cutoff[x]));
tree[x].max = cutoff[x];
// // cout << "yes " << tree[x].sum << endl;
}
cutoff[2 * x] = min(cutoff[2 * x], cutoff[x]);
cutoff[ 2 * x + 1] = min(cutoff[ 2 * x + 1], cutoff[x]);
reset(x);
}
void build(ll x, ll l, ll r) {
reset(x);
if (l == r) {
tree[x] = {t[l], 0, 1, t[l]};
// // // cout << t[l] << endl;
// // // cout << tree[x].max << " " << tree[x].freqmax << " " << l << endl;
// // // cout << "sum " << l << " " << tree[x].sum << endl;
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]);
// // // cout << l << " " << r << " " << tree[x].sum << endl;
}
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);
}
pair<ll, ll> combpair(pair<ll, ll> a, pair<ll, ll> b) {
if (a.first == b.first) {
return {a.first, a.second + b.second};
}
if (a.first > b.first) {
return a;
} else return b;
}
pair<ll, ll> getMaxInfo(ll x, ll l, ll r, ll ql, ll qr) {
pushdown(x, l, r);
if (ql <= l && r <= qr) return {tree[x].max, tree[x].freqmax};
if (l > qr || r < ql) return {0, 0};
ll mid = (l + r) / 2;
return combpair(getMaxInfo(2 * x, l, mid, ql, qr), getMaxInfo(2 * x + 1, mid + 1, r, ql, qr));
}
ll getSecondMax(ll x, ll l, ll r, ll ql, ll qr) {
pushdown(x, l, r);
if (ql <= l && r <= qr) return tree[x].smax;
if (l > qr || r < ql) return 0;
ll mid = (l + r) / 2;
return max(getSecondMax(2 * x, l, mid, ql, qr), getSecondMax(2 * x + 1, mid + 1, r, ql, qr));
}
ll getSum(ll x, ll l, ll r, ll ql, ll qr) {
pushdown(x, l, r);
if (ql <= l && r <= qr) return tree[x].sum;
if (l > qr || r < ql) return 0;
ll 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;
}
void lazy(ll x, ll l, ll r, ll ql, ll qr, ll lazyval) {
// // cout << ql << " " << qr << " " << lazyval << endl;
pushdown(x, l, r);
if (ql > r || qr < l || lazyval > tree[x].max) return;
if ((ql <= l && r <= qr && lazyval > tree[x].smax) || (l == r)) {
cutoff[x] = lazyval;
// // cout << "asdf " << l << " " << r << " " << lazyval << endl;
// cout << tree[x].sum << endl;
pushdown(x, l, r);
// cout << tree[x].sum << endl;
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, l, r);
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;
}
int mid = (l + r) / 2;
int 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) {
// // // cout << "firts seen " << endl;
// return;
while (k >= 0) {
auto maxinfo = getMaxInfo(1, 1, n, l, r);
ll smax = getSecondMax(1, 1, n, l, r);
if (maxinfo.first == 0) return;
ll curavail = (maxinfo.first - smax) * maxinfo.second;
if (k < curavail) {
// need to split it somewhere
ll lvls = k / maxinfo.second;
ll remains = k % maxinfo.second;
// cout << "bruh" << endl;
// cout << lvls << " " << remains << endl;
if (remains == 0) {
// // cout << "asdf " << maxinfo.first - lvls << endl;
lazy(1, 1, n, l, r, maxinfo.first - lvls);
} else {
k = 0;
ll idx = walkdown(1, 1, n, l, r, remains, maxinfo.first);
lazy(1, 1, n, l, idx, maxinfo.first - lvls - 1);
lazy(1, 1, n, idx + 1, r, maxinfo.first - lvls);
}
k = 0; break;
} else {
lazy(1, 1, n, l, r, smax);
k -= curavail;
}
}
return;
// // // cout << "cutdown " << endl;
}
void setbruh(ll x, ll l, ll r, ll i, ll xx) {
pushdown(x, l, r);
if (l == r) {
tree[x] = {xx, 0, 1, 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, l, mid);
pushdown(2 * x + 1, mid + 1, r);
// // cout << l << " " << r << endl;
// // cout << tree[2 * x].max << " " << tree[2 * x + 1].max << endl;
tree[x] = combine(tree[2 * x], tree[2 * x + 1]);
// // cout << tree[x].max << " " << tree[x].smax << " " << l << " " << r << endl;
}
void magic(int i, int x ) {
// // cout << "magic " << endl;
setbruh(1, 1, n, i, x);
}
ll inspect(int l, int r) {
// // cout << "inspect " << endl;
return getSum(1, 1, n, l, r);
}
Compilation message
weirdtree.cpp:166:3: warning: #warning may need to fix [-Wcpp]
166 | # warning may need to fix
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
91 ms |
13896 KB |
Output is correct |
| 4 |
Correct |
106 ms |
13868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
200 ms |
53120 KB |
Output is correct |
| 2 |
Correct |
278 ms |
53404 KB |
Output is correct |
| 3 |
Correct |
11 ms |
13604 KB |
Output is correct |
| 4 |
Correct |
88 ms |
13392 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
91 ms |
13896 KB |
Output is correct |
| 4 |
Correct |
106 ms |
13868 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
468 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
91 ms |
13896 KB |
Output is correct |
| 4 |
Correct |
106 ms |
13868 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
468 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
