Submission #1068468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068468		mickey080929	Weirdtree (RMI21_weirdtree)	C++17	100 / 100	546 ms	44464 KiB

weirdtree

#include "weirdtree.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

const ll inf = 2e18;

struct Node{
    ll mx, mx2, cnt, sum;
};

Node f(Node u, Node v) {
    if (u.mx == v.mx)
        return {u.mx, max(u.mx2, v.mx2), u.cnt + v.cnt, u.sum + v.sum};
    if (u.mx < v.mx) swap(u, v);
    return {u.mx, max(u.mx2, v.mx), u.cnt, u.sum + v.sum};
}

struct SegmentTree{
	vector<Node> tree;
	void init(ll n) {
		ll sz = 1 << __lg(n-1) + 2;
		tree.assign(sz, {0,0,0,0});
	}
	void push(ll node, ll s, ll e) {
	    if (s == e) return;
	    for (ll i : {node*2, node*2+1}) {
	        if (tree[node].mx < tree[i].mx) {
	            tree[i].sum -= (tree[i].mx - tree[node].mx) * tree[i].cnt;
	            tree[i].mx = tree[node].mx;
	        }
	    }
	}

	void modify(ll node, ll s, ll e, ll tar, ll val) {
		push(node, s, e);
		if (s > tar || tar > e) return;
		if (s == e) {
			tree[node] = {val, -1, 1, val};
			return;
		}
		ll mid = s + e >> 1;
		modify(node*2, s, mid, tar, val);
		modify(node*2+1, mid+1, e, tar, val);
		tree[node] = f(tree[node*2], tree[node*2+1]);
	}

	void update(ll node, ll s, ll e, ll l, ll r, ll v) {
	    push(node, s, e);
	    if (l > e || s > r || tree[node].mx <= v) return;
	    if (l <= s && e <= r && tree[node].mx2 < v) {
	        tree[node].sum -= (tree[node].mx - v) * tree[node].cnt;
	        tree[node].mx = v;
	        push(node, s, e);
	        return;
	    }
	    ll mid = s + e >> 1;
	    update(node*2, s, mid, l, r, v);
	    update(node*2+1, mid+1, e, l, r, v);
	    tree[node] = f(tree[node*2], tree[node*2+1]);
	}

	Node query(ll node, ll s, ll e, ll l, ll r) {
	    push(node, s, e);
	    if (l > e || s > r) return {-1, -1, 0, 0};
	    if (l <= s && e <= r) return tree[node];
	    ll mid = s + e >> 1;
	    return f(query(node*2, s, mid, l, r), query(node*2+1, mid+1, e, l, r));
	}

	pll findLeft(ll node, ll s, ll e, ll l, ll r, ll mx, ll k) {
		push(node, s, e);
		if (l > e || s > r) return {-1, 0};
		if (tree[node].mx < mx) return {-1, 0};
		if (tree[node].mx == mx && tree[node].cnt < k) return {-1, tree[node].cnt};
		if (s == e) return {s, 0};
		ll mid = s + e >> 1;
		pll t1 = findLeft(node*2, s, mid, l, r, mx, k);
		if (t1.first == -1) {
			pll t2 = findLeft(node*2+1, mid+1, e, l, r, mx, k - t1.second);
			return {t2.first, t1.second + t2.second};
		}
		return t1;
	}
};

SegmentTree seg;

ll n;

void initialise(int N, int Q, int h[]) {
	n = N;
	seg.init(N);
	for (ll i=1; i<=N; i++) {
		seg.modify(1, 1, N, i, h[i]);
	}
}

void cut(int l, int r, int _k) {
	ll k = _k;
	while (true) {
		Node ret = seg.query(1, 1, n, l, r);
		if (ret.mx == 0) break;
		ret.mx2 = max(ret.mx2, 0LL);
		if ((ret.mx - ret.mx2) * ret.cnt <= k) {
			seg.update(1, 1, n, l, r, ret.mx2);
			k -= (ret.mx - ret.mx2) * ret.cnt;
			continue;
		}
		ll diff = k / ret.cnt;
		seg.update(1, 1, n, l, r, ret.mx - diff);
		k %= ret.cnt;
		if (k == 0) break;
		ll idx = seg.findLeft(1, 1, n, l, r, ret.mx - diff, k).first;
		assert(idx != -1);
		seg.update(1, 1, n, l, idx, ret.mx - diff - 1);
		break;
	}
}

void magic(int i, int x) {
	seg.modify(1, 1, n, i, x);
}
long long int inspect(int l, int r) {
	return seg.query(1, 1, n, l, r).sum;
}

Compilation message (stderr)

weirdtree.cpp: In member function 'void SegmentTree::init(ll)':
weirdtree.cpp:24:26: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   24 |   ll sz = 1 << __lg(n-1) + 2;
      |                ~~~~~~~~~~^~~
weirdtree.cpp: In member function 'void SegmentTree::modify(ll, ll, ll, ll, ll)':
weirdtree.cpp:44:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |   ll mid = s + e >> 1;
      |            ~~^~~
weirdtree.cpp: In member function 'void SegmentTree::update(ll, ll, ll, ll, ll, ll)':
weirdtree.cpp:59:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |      ll mid = s + e >> 1;
      |               ~~^~~
weirdtree.cpp: In member function 'Node SegmentTree::query(ll, ll, ll, ll, ll)':
weirdtree.cpp:69:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |      ll mid = s + e >> 1;
      |               ~~^~~
weirdtree.cpp: In member function 'pll SegmentTree::findLeft(ll, ll, ll, ll, ll, ll, ll)':
weirdtree.cpp:79:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |   ll mid = s + e >> 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