#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 300005;
int nums;
ll height[MAXN];
struct vals{
ll mx1, mx2, cnt1, sum;
};
vals st[MAXN * 2];
ll lazy[MAXN * 2];
vals join(vals a, vals b){
vals res;
if (a.mx1 > b.mx1){
res.mx1 = a.mx1;
res.mx2 = max(a.mx2, b.mx1);
res.cnt1 = a.cnt1;
}
else if (a.mx1 < b.mx1){
res.mx1 = b.mx1;
res.mx2 = max(a.mx1, b.mx2);
res.cnt1 = b.cnt1;
}
else{
res.mx1 = a.mx1;
res.mx2 = max(a.mx2, b.mx2);
res.cnt1 = a.cnt1 + b.cnt1;
}
res.sum = a.sum + b.sum;
return res;
}
void init(int ind, int s, int e){
lazy[ind] = -1;
if (s == e){
st[ind] = {height[s], -1, 1, height[s]};
return;
}
int m = (s + e) >> 1;
init(ind << 1, s, m);
init((ind << 1) + 1, m + 1, e);
st[ind] = join(st[ind << 1], st[(ind << 1) + 1]);
}
int finalv(int ind){
return (lazy[ind] == -1 ? st[ind].mx1 : lazy[ind]);
}
void propo(int ind, bool leaf){
if (lazy[ind] == -1) return;
if (!leaf){
if (finalv(ind << 1) == st[ind].mx1) lazy[ind << 1] = lazy[ind];
if (finalv((ind << 1) + 1) == st[ind].mx1) lazy[(ind << 1) + 1] = lazy[ind];
}
st[ind].sum -= st[ind].cnt1 * (st[ind].mx1 - lazy[ind]);
st[ind].mx1 = lazy[ind];
lazy[ind] = -1;
}
void updatemin(int ind, int s, int e, int l, int r, ll v){
propo(ind, s == e);
if (v >= st[ind].mx1) return;
if (l == s && r == e){
if (v > st[ind].mx2){
lazy[ind] = v;
return;
}
}
int m = (s + e) >> 1;
if (l <= m) updatemin(ind << 1, s, m, l, min(r, m), v);
if (r > m) updatemin((ind << 1) + 1, m + 1, e, max(l, m + 1), r, v);
propo(ind << 1, s == m); propo((ind << 1) + 1, m + 1 == e);
st[ind] = join(st[ind << 1], st[(ind << 1) + 1]);
}
void updateset(int ind, int s, int e, int p, ll v){
propo(ind, s == e);
if (s == e){
st[ind] = {v, -1, 1, v};
return;
}
int m = (s + e) >> 1;
if (p <= m) updateset(ind << 1, s, m, p, v);
else updateset((ind << 1) + 1, m + 1, e, p, v);
propo(ind << 1, s == m); propo((ind << 1) + 1, m + 1 == e);
st[ind] = join(st[ind << 1], st[(ind << 1) + 1]);
}
vals query(int ind, int s, int e, int l, int r){
propo(ind, s == e);
int m = (s + e) >> 1;
if (l == s && r == e) return st[ind];
else if (r <= m) return query(ind << 1, s, m, l, r);
else if (l > m) return query((ind << 1) + 1, m + 1, e, l, r);
else return join(query(ind << 1, s, m, l, m), query((ind << 1) + 1, m + 1, e, m + 1, r));
}
int findkth(int ind, int s, int e, int l, int r, int &k, ll v){
propo(ind, s == e);
if (st[ind].mx1 < v) return -1;
if (l == s && r == e){
if (st[ind].cnt1 < k){
k -= st[ind].cnt1;
return -1;
}
}
if (s == e) return s;
int m = (s + e) >> 1;
if (r <= m) return findkth(ind << 1, s, m, l, r, k, v);
else if (l > m) return findkth((ind << 1) + 1, m + 1, e, l, r, k, v);
else{
int lres = findkth(ind << 1, s, m, l, m, k, v);
if (lres != -1) return lres;
return findkth((ind << 1) + 1, m + 1, e, m + 1, r, k, v);
}
}
void initialise(int N, int Q, int h[]) {
nums = N;
for (int i = 1; i <= N; i++) height[i] = h[i];
init(1, 1, nums);
}
void cut(int l, int r, int k) {
while (k > 0){
vals v = query(1, 1, nums, l, r);
if (v.mx1 == 0) break;
if (k >= v.sum){
updatemin(1, 1, nums, l, r, 0);
break;
}
else if (k >= v.cnt1 * (v.mx1 - v.mx2)){
updatemin(1, 1, nums, l, r, v.mx2);
k -= v.cnt1 * (v.mx1 - v.mx2);
}
else{
int quot = k / v.cnt1, rem = k % v.cnt1;
if (rem == 0) updatemin(1, 1, nums, l, r, v.mx1 - quot);
else{
int remind = findkth(1, 1, nums, l, r, rem, v.mx1);
assert(remind != -1);
updatemin(1, 1, nums, l, remind, v.mx1 - quot - 1);
updatemin(1, 1, nums, remind + 1, r, v.mx1 - quot);
}
k = 0;
}
}
}
void magic(int i, int x) {
updateset(1, 1, nums, i, x);
}
ll inspect(int l, int r) {
return query(1, 1, nums, l, r).sum;
}
| # |
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 |
61 ms |
11944 KB |
Output is correct |
| 4 |
Correct |
72 ms |
12108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
468 KB |
Output is correct |
| 2 |
Correct |
3 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
468 KB |
Output is correct |
| 2 |
Correct |
3 ms |
468 KB |
Output is correct |
| 3 |
Runtime error |
24 ms |
29944 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
24 ms |
26856 KB |
Execution killed with signal 11 |
| 2 |
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 |
61 ms |
11944 KB |
Output is correct |
| 4 |
Correct |
72 ms |
12108 KB |
Output is correct |
| 5 |
Correct |
3 ms |
468 KB |
Output is correct |
| 6 |
Correct |
3 ms |
468 KB |
Output is correct |
| 7 |
Correct |
75 ms |
13860 KB |
Output is correct |
| 8 |
Correct |
79 ms |
13900 KB |
Output is correct |
| 9 |
Correct |
65 ms |
13888 KB |
Output is correct |
| 10 |
Correct |
79 ms |
14000 KB |
Output is correct |
| 11 |
Correct |
70 ms |
13924 KB |
Output is correct |
| 12 |
Correct |
13 ms |
13636 KB |
Output is correct |
| 13 |
Correct |
48 ms |
13264 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 |
61 ms |
11944 KB |
Output is correct |
| 4 |
Correct |
72 ms |
12108 KB |
Output is correct |
| 5 |
Correct |
3 ms |
468 KB |
Output is correct |
| 6 |
Correct |
3 ms |
468 KB |
Output is correct |
| 7 |
Runtime error |
24 ms |
29944 KB |
Execution killed with signal 11 |
| 8 |
Halted |
0 ms |
0 KB |
- |
