#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
#define REP(i, j, k) for (int i = j; i < k; i++)
#define RREP(i, j, k) for (int i = j; i >= k; i--)
template <class T>
inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int) x.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef tuple<int, int, int> iii;
typedef vector<iii> viii;
#ifndef DEBUG
#define cerr if(0) cerr
#endif
const int INF = 1000000005;
const ll LINF = 1000000000000000005;
const int MAXN = 300005;
int n;
int h[MAXN];
ll sm[MAXN * 4];
int mx[MAXN * 4], mxc[MAXN * 4], smx[MAXN * 4], lz[MAXN * 4];
#define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
void propo(int u, int lo, int hi) {
if (lz[u] == 0) {
return;
}
MLR;
if (mx[u] + lz[u] == mx[lc]) {
mx[lc] -= lz[u];
sm[lc] -= (ll) lz[u] * mxc[lc];
lz[lc] += lz[u];
}
if (mx[u] + lz[u] == mx[rc]) {
mx[rc] -= lz[u];
sm[rc] -= (ll) lz[u] * mxc[rc];
lz[rc] += lz[u];
}
lz[u] = 0;
}
void merge(int u, int lo, int hi) {
MLR;
if (mx[lc] == mx[rc]) {
mx[u] = mx[lc];
mxc[u] = mxc[lc] + mxc[rc];
smx[u] = max(smx[lc], smx[rc]);
} else if (mx[lc] > mx[rc]) {
mx[u] = mx[lc];
mxc[u] = mxc[lc];
smx[u] = max(smx[lc], mx[rc]);
} else {
mx[u] = mx[rc];
mxc[u] = mxc[rc];
smx[u] = max(smx[rc], mx[lc]);
}
sm[u] = sm[lc] + sm[rc];
}
void init(int u = 1, int lo = 1, int hi = n) {
lz[u] = 0;
if (lo == hi) {
sm[u] = h[lo];
mx[u] = h[lo];
mxc[u] = 1;
smx[u] = -1;
return;
}
MLR;
init(lc, lo, mid);
init(rc, mid + 1, hi);
merge(u, lo, hi);
}
void upd(int p, int x, int u = 1, int lo = 1, int hi = n) {
if (lo == hi) {
sm[u] = x;
mx[u] = x;
mxc[u] = 1;
smx[u] = -1;
return;
}
MLR;
propo(u, lo, hi);
if (p <= mid) {
upd(p, x, lc, lo, mid);
} else {
upd(p, x, rc, mid + 1, hi);
}
merge(u, lo, hi);
}
void updmn(int s, int e, int x, int u = 1, int lo = 1, int hi = n) {
if (mx[u] <= x) {
return;
}
if (lo >= s && hi <= e && smx[u] < x) {
lz[u] += mx[u] - x;
sm[u] -= (ll) (mx[u] - x) * mxc[u];
mx[u] = x;
return;
}
MLR;
propo(u, lo, hi);
if (s <= mid) {
updmn(s, e, x, lc, lo, mid);
}
if (e > mid) {
updmn(s, e, x, rc, mid + 1, hi);
}
merge(u, lo, hi);
}
iii qmx(int s, int e, int u = 1, int lo = 1, int hi = n) {
if (lo >= s && hi <= e) {
return {mx[u], mxc[u], smx[u]};
}
MLR;
propo(u, lo, hi);
if (e <= mid) {
return qmx(s, e, lc, lo, mid);
} else if (s > mid) {
return qmx(s, e, rc, mid + 1, hi);
} else {
auto [lmx, lmxc, lsmx] = qmx(s, e, lc, lo, mid);
auto [rmx, rmxc, rsmx] = qmx(s, e, rc, mid + 1, hi);
int mx, mxc, smx;
if (lmx == rmx) {
mx = lmx;
mxc = lmxc + rmxc;
smx = max(lsmx, rsmx);
} else if (lmx > rmx) {
mx = lmx;
mxc = lmxc;
smx = max(lsmx, rmx);
} else {
mx = rmx;
mxc = rmxc;
smx = max(rsmx, lmx);
}
return {mx, mxc, smx};
}
}
ll qsm(int s, int e, int u = 1, int lo = 1, int hi = n) {
cerr << " " << lo << ' ' << hi << ": " << sm[u] << '\n';
if (lo >= s && hi <= e) {
return sm[u];
}
MLR;
propo(u, lo, hi);
ll res = 0;
if (s <= mid) {
res += qsm(s, e, lc, lo, mid);
}
if (e > mid) {
res += qsm(s, e, rc, mid + 1, hi);
}
return res;
}
int lb(int s, int x, int &c, int u = 1, int lo = 1, int hi = n) {
if (lo == hi) {
return lo;
}
MLR;
propo(u, lo, hi);
if (mid < s) {
return lb(s, x, c, rc, mid + 1, hi);
} else if (lo < s) {
int res = lb(s, x, c, lc, lo, mid);
if (c == 0) {
return res;
}
return lb(s, x, c, rc, mid + 1, hi);
} else {
if (mx[lc] != x) {
return lb(s, x, c, rc, mid + 1, hi);
}
if (mxc[lc] <= c) {
c -= mxc[lc];
return lb(s, x, c, rc, mid + 1, hi);
} else {
return lb(s, x, c, lc, lo, mid);
}
}
}
void initialise(int N, int Q, int H[]) {
n = N;
REP (i, 1, n + 1) {
h[i] = H[i];
}
init();
}
void cut(int l, int r, int k) {
cerr << "CUT " << l << ' ' << r << ' ' << k << '\n';
while (k) {
auto [mx, mxc, smx] = qmx(l, r);
cerr << mx << ' ' << smx << ' ' << mxc << '\n';
if (mx == 0) {
break;
}
mxto(smx, 0);
if ((ll) (mx - smx) * mxc <= k) {
k -= (ll) (mx - smx) * mxc;
cerr << " UPDMN: " << l << ' ' << r << ' ' << smx << '\n';
updmn(l, r, smx);
continue;
}
int d = k / mxc, ex = k % mxc;
if (ex == 0) {
updmn(l, r, mx - d);
k = 0;
break;
}
int p = lb(l, mx, ex);
cerr << " UPDMN: " << l << ' ' << p - 1 << ' ' << mx - d - 1 << '\n';
cerr << " UPDMN: " << p << ' ' << r << ' ' << mx - d << '\n';
assert(p <= r);
updmn(l, p - 1, mx - d - 1);
updmn(p, r, mx - d);
k = 0;
}
}
void magic(int i, int x) {
cerr << "UPD " << i << ' ' << x << '\n';
upd(i, x);
}
long long int inspect(int l, int r) {
return qsm(l, r);
}
Compilation message
weirdtree.cpp: In function 'void propo(int, int, int)':
weirdtree.cpp:42:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
42 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
weirdtree.cpp:47:5: note: in expansion of macro 'MLR'
47 | MLR;
| ^~~
weirdtree.cpp:42:17: warning: unused variable 'mid' [-Wunused-variable]
42 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
| ^~~
weirdtree.cpp:47:5: note: in expansion of macro 'MLR'
47 | MLR;
| ^~~
weirdtree.cpp: In function 'void merge(int, int, int)':
weirdtree.cpp:42:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
42 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
weirdtree.cpp:61:5: note: in expansion of macro 'MLR'
61 | MLR;
| ^~~
weirdtree.cpp:42:17: warning: unused variable 'mid' [-Wunused-variable]
42 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
| ^~~
weirdtree.cpp:61:5: note: in expansion of macro 'MLR'
61 | MLR;
| ^~~
weirdtree.cpp: In function 'void init(int, int, int)':
weirdtree.cpp:42:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
42 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
weirdtree.cpp:86:5: note: in expansion of macro 'MLR'
86 | MLR;
| ^~~
weirdtree.cpp: In function 'void upd(int, int, int, int, int)':
weirdtree.cpp:42:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
42 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
weirdtree.cpp:99:5: note: in expansion of macro 'MLR'
99 | MLR;
| ^~~
weirdtree.cpp: In function 'void updmn(int, int, int, int, int, int)':
weirdtree.cpp:42:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
42 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
weirdtree.cpp:118:5: note: in expansion of macro 'MLR'
118 | MLR;
| ^~~
weirdtree.cpp: In function 'iii qmx(int, int, int, int, int)':
weirdtree.cpp:42:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
42 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
weirdtree.cpp:132:5: note: in expansion of macro 'MLR'
132 | MLR;
| ^~~
weirdtree.cpp: In function 'll qsm(int, int, int, int, int)':
weirdtree.cpp:42:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
42 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
weirdtree.cpp:163:5: note: in expansion of macro 'MLR'
163 | MLR;
| ^~~
weirdtree.cpp: In function 'int lb(int, int, int&, int, int, int)':
weirdtree.cpp:42:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
42 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
weirdtree.cpp:178:5: note: in expansion of macro 'MLR'
178 | MLR;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
55 ms |
7544 KB |
Output is correct |
| 4 |
Runtime error |
13 ms |
14360 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
724 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
724 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
135 ms |
28796 KB |
Output is correct |
| 2 |
Correct |
163 ms |
28940 KB |
Output is correct |
| 3 |
Correct |
9 ms |
7124 KB |
Output is correct |
| 4 |
Correct |
38 ms |
7124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
55 ms |
7544 KB |
Output is correct |
| 4 |
Runtime error |
13 ms |
14360 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
55 ms |
7544 KB |
Output is correct |
| 4 |
Runtime error |
13 ms |
14360 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
