#include <bits/stdc++.h>
#include "weirdtree.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e12; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }
int n;
const int N = 3e5 + 100;
struct node {
ll s, mx, smx, cmx;
node(int x = 0) : s(x), mx(x) { cmx = 1; smx = -inf; }
} t[4 * N];
inline node merge(const node &a, const node &b) {
node res;
res.s = a.s + b.s;
res.mx = max(a.mx, b.mx);
res.cmx = (a.mx == res.mx ? a.cmx : 0) + (b.mx == res.mx ? b.cmx : 0);
res.smx = max(a.smx, b.smx);
if (a.mx != res.mx) chmax(res.smx, a.mx);
if (b.mx != res.mx) chmax(res.smx, b.mx);
return res;
}
inline void mg(int v) { t[v] = merge(t[2 * v + 1], t[2 * v + 2]); }
inline void cmin(int v, int x) {
if (t[v].mx > x) {
t[v].s -= (t[v].mx - x) * 1ll * t[v].cmx;
t[v].mx = x;
}
}
inline void push(int v) {
for (int u : {2 * v + 1, 2 * v + 2}) {
cmin(u, t[v].mx);
}
}
inline void build(int v, int vl, int vr, int *h) {
if (vl == vr) return void(t[v] = node(h[vl + 1]));
int m = vl + vr >> 1;
build(2 * v + 1, vl, m, h);
build(2 * v + 2, m + 1, vr, h);
mg(v);
}
inline void uset(int v, int vl, int vr, int pos, int x) {
if (vl == vr) return void(t[v] = node(x));
push(v);
int m = vl + vr >> 1;
if (pos <= m) uset(2 * v + 1, vl, m, pos, x);
else uset(2 * v + 2, m + 1, vr, pos, x);
mg(v);
}
inline void umin(int v, int vl, int vr, int l, int r, int x) {
if (l > r || t[v].mx <= x) return;
else if (vl == l && vr == r && t[v].smx < x) {
cmin(v, x); return;
}
push(v);
int m = vl + vr >> 1;
umin(2 * v + 1, vl, m, l, min(r, m), x);
umin(2 * v + 2, m + 1, vr, max(l, m + 1), r, x);
mg(v);
}
inline void uadd(int v, int vl, int vr, int l, int r, int &x) {
if (l > r || !x || !t[v].mx) return;
else if (vl == l && vr == r && t[v].mx - 1 > t[v].smx && x >= t[v].cmx) {
cmin(v, t[v].mx - 1);
x -= t[v].cmx;
return;
}
push(v);
int m = vl + vr >> 1;
uadd(2 * v + 1, vl, m, l, min(r, m), x);
uadd(2 * v + 2, m + 1, vr, max(l, m + 1), r, x);
mg(v);
}
inline node get(int v, int vl, int vr, int l, int r) {
if (vl == l && vr == r) return t[v];
push(v);
int m = vl + vr >> 1;
if (r <= m) return get(2 * v + 1, vl, m, l, r);
else if (l > m) return get(2 * v + 2, m + 1, vr, l, r);
else {
node a = get(2 * v + 1, vl, m, l, min(r, m));
node b = get(2 * v + 2, m + 1, vr, max(l, m + 1), r);
return merge(a, b);
}
}
void initialise(int N, int Q, int h[]) {
n = N;
build(0, 0, n - 1, h);
}
void cut(int l, int r, int k) { --l, --r;
while (k) {
node cur = get(0, 0, n - 1, l, r);
// cout << l + 1 << " " << r + 1 << ": " << cur.mx << " " << cur.cmx << " " << cur.smx << '\n';
if (cur.mx == 0) break;
if (cur.cmx * (cur.mx - cur.smx) <= k) {
k -= cur.cmx * (cur.mx - cur.smx);
umin(0, 0, n - 1, l, r, cur.smx);
}
else {
ll newv = cur.mx - (k / cur.cmx);
umin(0, 0, n - 1, l, r, newv);
k %= cur.cmx;
uadd(0, 0, n - 1, l, r, k);
k = 0;
}
}
}
void magic(int i, int x) {
uset(0, 0, n - 1, --i, x);
}
long long int inspect(int l, int r) {
return get(0, 0, n - 1, --l, --r).s;
}
#ifdef LOCAL
int main() {
int N, Q;
cin >> N >> Q;
int h[N + 1];
for (int i = 1; i <= N; ++i) cin >> h[i];
initialise(N, Q, h);
for (int i = 1; i <= Q; ++i) {
int t;
cin >> t;
if (t == 1) {
int l, r, k;
cin >> l >> r >> k;
cut(l, r, k);
} else if (t == 2) {
int i, x;
cin >> i >> x;
magic(i, x);
} else {
int l, r;
cin >> l >> r;
cout << inspect(l, r) << '\n';
}
}
return 0;
}
#endif
Compilation message
weirdtree.cpp: In function 'void build(int, int, int, int*)':
weirdtree.cpp:57:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
57 | int m = vl + vr >> 1;
| ~~~^~~~
weirdtree.cpp: In function 'void uset(int, int, int, int, int)':
weirdtree.cpp:65:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | int m = vl + vr >> 1;
| ~~~^~~~
weirdtree.cpp: In function 'void umin(int, int, int, int, int, int)':
weirdtree.cpp:76:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
76 | int m = vl + vr >> 1;
| ~~~^~~~
weirdtree.cpp: In function 'void uadd(int, int, int, int, int, int&)':
weirdtree.cpp:89:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
89 | int m = vl + vr >> 1;
| ~~~^~~~
weirdtree.cpp: In function 'node get(int, int, int, int, int)':
weirdtree.cpp:98:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
98 | int m = vl + vr >> 1;
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
37956 KB |
Output is correct |
| 2 |
Correct |
17 ms |
37844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
37956 KB |
Output is correct |
| 2 |
Correct |
17 ms |
37844 KB |
Output is correct |
| 3 |
Correct |
65 ms |
40700 KB |
Output is correct |
| 4 |
Incorrect |
75 ms |
40624 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
37976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
37976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
47544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
37956 KB |
Output is correct |
| 2 |
Correct |
17 ms |
37844 KB |
Output is correct |
| 3 |
Correct |
65 ms |
40700 KB |
Output is correct |
| 4 |
Incorrect |
75 ms |
40624 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
37956 KB |
Output is correct |
| 2 |
Correct |
17 ms |
37844 KB |
Output is correct |
| 3 |
Correct |
65 ms |
40700 KB |
Output is correct |
| 4 |
Incorrect |
75 ms |
40624 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
