Submission #573492

#	Time	Username	Problem	Language	Result	Execution time	Memory
573492		vovamr	Weirdtree (RMI21_weirdtree)	C++17	100 / 100	345 ms	49052 KiB

weirdtree

#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, ll need, int &x) {
	if (l > r || !x || t[v].mx < need) 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), need, x);
	uadd(2 * v + 2, m + 1, vr, max(l, m + 1), r, need, 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, m);
		node b = get(2 * v + 2, m + 1, vr, 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);

		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 = max(0ll, cur.mx - (k / cur.cmx));
			umin(0, 0, n - 1, l, r, newv);
			k %= cur.cmx;
			uadd(0, 0, n - 1, l, r, newv, k);
		}
	}
}
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 (stderr)

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, long long int, int&)':
weirdtree.cpp:88:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |  int m = vl + vr >> 1;
      |          ~~~^~~~
weirdtree.cpp: In function 'node get(int, int, int, int, int)':
weirdtree.cpp:97:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |  int m = vl + vr >> 1;
      |          ~~~^~~~

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 19 / 19
• Subtask 5: 10 / 10
• Subtask 6: 21 / 21
• Subtask 7: 29 / 29