#include "weirdtree.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
typedef long long llong;
const int MAXN = 300000 + 10;
const int INF = 2e9;
int n, q;
int a[MAXN];
struct Number
{
int value, count;
Number()
{
value = -1;
count = 0;
}
Number(int _value, int _count)
{
value = _value;
count = _count;
}
inline friend bool operator < (const Number &a, const Number &b)
{
return a.value < b.value;
}
inline friend bool operator == (const Number &a, const Number &b)
{
return a.value == b.value;
}
inline friend bool operator != (const Number &a, const Number &b)
{
return !(a == b);
}
inline friend bool operator > (const Number &a, const Number &b)
{
return a.value > b.value;
}
inline friend void operator += (Number &a, const Number &b)
{
if (a.value == b.value) a.count += b.count;
if (a.value < b.value) a = b;
}
};
struct Node
{
Number max, max2;
llong sum;
Node()
{
max = max2 = {-1, 0};
sum = 0;
}
} tree[4*MAXN];
inline Node combine(Node left, Node right)
{
Node result;
result.sum = left.sum + right.sum;
result.max = left.max;
result.max += right.max;
if (left.max != result.max)
{
result.max2 = left.max;
} else
{
result.max2 = left.max2;
}
if (right.max != result.max)
{
result.max2 += right.max;
} else
{
result.max2 += right.max2;
}
return result;
}
void build(int l, int r, int node)
{
if (l == r)
{
tree[node].max2 = {-1, 0};
tree[node].max = {a[l], 1};
tree[node].sum = a[l];
return;
}
int mid = (l + r) / 2;
build(l, mid, 2*node);
build(mid + 1, r, 2*node + 1);
tree[node] = combine(tree[2*node], tree[2*node + 1]);
}
Node query(int l, int r, int node, int queryL, int queryR)
{
if (queryL <= l && r <= queryR)
{
return tree[node];
}
Node res;
int mid = (l + r) / 2;
if (queryL <= mid) res = combine(res, query(l, mid, 2*node, queryL, queryR));
if (mid + 1 <= queryR) res = combine(res, query(mid + 1, r, 2*node + 1, queryL, queryR));
return res;
}
void updatePos(int l, int r, int node, int queryPos, int queryVal)
{
if (l == r)
{
tree[node].max2 = {-1, 0};
tree[node].max = {queryVal, 1};
tree[node].sum = queryVal;
return;
}
int mid = (l + r) / 2;
if (queryPos <= mid) updatePos(l, mid, 2*node, queryPos, queryVal);
else updatePos(mid + 1, r, 2*node + 1, queryPos, queryVal);
tree[node] = combine(tree[2*node], tree[2*node + 1]);
}
int toRemove;
int searchedMax;
int findFirstPos(int l, int r, int node, int queryL, int queryR)
{
if (tree[node].max.value < searchedMax) return -1;
if (l == r)
{
assert(queryL <= l && r <= queryR);
if (searchedMax != tree[node].max.value) return -1;
if (toRemove != 1)
{
toRemove--;
return -1;
}
return l;
}
if (queryL <= l & r <= queryR)
{
if (searchedMax != tree[node].max.value || tree[node].max.count < toRemove)
{
if (searchedMax == tree[node].max.value) toRemove -= tree[node].max.count;
return -1;
}
int mid = (l + r) / 2;
if (tree[node].max.value == tree[2*node].max.value && toRemove <= tree[2*node].max.count)
{
return findFirstPos(l, mid, 2*node, queryL, queryR);
}
if (searchedMax == tree[2*node].max.value) toRemove -= tree[2*node].max.count;
return findFirstPos(mid + 1, r, 2*node + 1, queryL, queryR);
}
int mid = (l + r) / 2;
if (queryL <= mid)
{
int res = findFirstPos(l, mid, 2*node, queryL, queryR);
if (res != -1) return res;
}
return findFirstPos(mid + 1, r, 2*node + 1, queryL, queryR);
}
void updateMAXminus(int l, int r, int node, int queryL, int queryR, int value)
{
if (tree[node].max.value < searchedMax) return;
if (queryL <= l && r <= queryR)
{
tree[node].sum -= 1LL * tree[node].max.count * value;
tree[node].max.value -= value;
if (l < r)
{
int mid = (l + r) / 2;
updateMAXminus(l, mid, 2*node, queryL, queryR, value);
updateMAXminus(mid + 1, r, 2*node + 1, queryL, queryR, value);
tree[node] = combine(tree[2*node], tree[2*node + 1]);
}
return;
}
int mid = (l + r) / 2;
if (queryL <= mid) updateMAXminus(l, mid, 2*node, queryL, queryR, value);
if (mid + 1 <= queryR) updateMAXminus(mid + 1, r, 2*node + 1, queryL, queryR, value);
tree[node] = combine(tree[2*node], tree[2*node + 1]);
}
Node original;
void updateMAX(int l, int r, int node, int queryL, int queryR)
{
if (tree[node].max < original.max) return;
if (queryL > l || r > queryR)
{
int mid = (l + r) / 2;
if (queryL <= mid) updateMAX(l, mid, 2*node, queryL, queryR);
if (mid + 1 <= queryR) updateMAX(mid + 1, r, 2*node + 1, queryL, queryR);
tree[node] = combine(tree[2*node], tree[2*node + 1]);
return;
}
if (tree[node].max2 != original.max2)
{
if (tree[node].max == original.max)
{
tree[node].sum -= 1LL * (tree[node].max.value - original.max2.value) * tree[node].max.count;
tree[node].max.value = original.max2.value;
if (l != r)
{
int mid = (l + r) / 2;
updateMAX(l, mid, 2*node, queryL, queryR);
updateMAX(mid + 1, r, 2*node + 1, queryL, queryR);
tree[node] = combine(tree[2*node], tree[2*node + 1]);
}
}
return;
}
tree[node].sum -= 1LL * (tree[node].max.value - original.max2.value) * tree[node].max.count;
tree[node].max.value = original.max2.value;
if (tree[node].max2 == original.max2) tree[node].max.count += tree[node].max2.count;
tree[node].max2 = {-1, 0};
if (l != r)
{
int mid = (l + r) / 2;
updateMAX(l, mid, 2*node, queryL, queryR);
updateMAX(mid + 1, r, 2*node + 1, queryL, queryR);
tree[node] = combine(tree[2*node], tree[2*node + 1]);
}
}
void initialise(int N, int Q, int h[])
{
n = N;
q = Q;
for (int i = 1 ; i <= n ; ++i)
{
a[i] = h[i];
}
build(1, n, 1);
}
void cut(int l, int r, int k)
{
while (k >= 1)
{
original = query(1, n, 1, l, r);
if (original.max.value == 0) return;
if (original.max2.value != -1 && k >= 1LL * (original.max.value - original.max2.value) * original.max.count)
{
// std::cerr << "here :)\n";
k -= 1LL * (original.max.value - original.max2.value) * original.max.count;
updateMAX(1, n, 1, l, r);
Node res = query(1, n, 1, l, r);
} else
{
bool firstIf = false;
if (original.max2.value == -1)
{
firstIf = true;
original.max2.value = 0;
if (k > 1LL * original.max.value * original.max.count)
{
k = 1LL * original.max.value * original.max.count;
}
}
if (firstIf || k <= 1LL * (original.max.value - original.max2.value - 1) * original.max.count)
{
searchedMax = original.max.value;
updateMAXminus(1, n, 1, l, r, k / original.max.count);
searchedMax = original.max.value - k / original.max.count;
k %= original.max.count;
if (k != 0)
{
toRemove = k;
int firstPos = findFirstPos(1, n, 1, l, r);
updateMAXminus(1, n, 1, l, firstPos, 1);
k = 0;
}
} else
{
searchedMax = original.max.value;
updateMAXminus(1, n, 1, l, r, (original.max.value - original.max2.value - 1));
k %= original.max.count;
if (k == 0)
{
k = original.max.count;
}
if (k != 0)
{
toRemove = k;
searchedMax = original.max2.value + 1;
int firstPos = findFirstPos(1, n, 1, l, r);
updateMAX(1, n, 1, l, firstPos);
}
k = 0;
}
}
}
}
void magic(int i, int x)
{
updatePos(1, n, 1, i, x);
}
llong inspect(int l, int r)
{
return query(1, n, 1, l, r).sum;
}
Compilation message
weirdtree.cpp: In function 'int findFirstPos(int, int, int, int, int)':
weirdtree.cpp:162:16: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
162 | if (queryL <= l & r <= queryR)
| ~~~~~~~^~~~
weirdtree.cpp: In function 'void cut(int, int, int)':
weirdtree.cpp:281:18: warning: variable 'res' set but not used [-Wunused-but-set-variable]
281 | Node res = query(1, n, 1, l, r);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
28500 KB |
Output is correct |
| 2 |
Correct |
15 ms |
28436 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
28500 KB |
Output is correct |
| 2 |
Correct |
15 ms |
28436 KB |
Output is correct |
| 3 |
Correct |
92 ms |
29652 KB |
Output is correct |
| 4 |
Correct |
112 ms |
29560 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
28500 KB |
Output is correct |
| 2 |
Correct |
23 ms |
28540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
28500 KB |
Output is correct |
| 2 |
Correct |
23 ms |
28540 KB |
Output is correct |
| 3 |
Correct |
1289 ms |
33200 KB |
Output is correct |
| 4 |
Correct |
368 ms |
33116 KB |
Output is correct |
| 5 |
Correct |
1338 ms |
33200 KB |
Output is correct |
| 6 |
Correct |
400 ms |
33100 KB |
Output is correct |
| 7 |
Execution timed out |
2095 ms |
29140 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2095 ms |
29140 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
28500 KB |
Output is correct |
| 2 |
Correct |
15 ms |
28436 KB |
Output is correct |
| 3 |
Correct |
92 ms |
29652 KB |
Output is correct |
| 4 |
Correct |
112 ms |
29560 KB |
Output is correct |
| 5 |
Correct |
19 ms |
28500 KB |
Output is correct |
| 6 |
Correct |
23 ms |
28540 KB |
Output is correct |
| 7 |
Execution timed out |
2095 ms |
29140 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
28500 KB |
Output is correct |
| 2 |
Correct |
15 ms |
28436 KB |
Output is correct |
| 3 |
Correct |
92 ms |
29652 KB |
Output is correct |
| 4 |
Correct |
112 ms |
29560 KB |
Output is correct |
| 5 |
Correct |
19 ms |
28500 KB |
Output is correct |
| 6 |
Correct |
23 ms |
28540 KB |
Output is correct |
| 7 |
Correct |
1289 ms |
33200 KB |
Output is correct |
| 8 |
Correct |
368 ms |
33116 KB |
Output is correct |
| 9 |
Correct |
1338 ms |
33200 KB |
Output is correct |
| 10 |
Correct |
400 ms |
33100 KB |
Output is correct |
| 11 |
Execution timed out |
2095 ms |
29140 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
