Submission #786738

#	Time	Username	Problem	Language	Result	Execution time	Memory
786738		flappybird	Weirdtree (RMI21_weirdtree)	C++17	100 / 100	1004 ms	54944 KiB

weirdtree

#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;

#define MAX 301010
typedef long long ll;

struct node {
	ll sum;
	ll mx;
	ll cnt;
	ll mx2;
	node(ll x) {
		sum = mx = x;
		cnt = 1;
		mx2 = -1e18;
	}
	node() {
		cnt = -1;
		sum = 0;
		mx = mx2 = 0;
	}
};

node operator+(node n1, node n2) {
	if (!~n1.cnt) return n2;
	if (!~n2.cnt) return n1;
	node ret;
	ret.sum = n1.sum + n2.sum;
	ret.mx = max(n1.mx, n2.mx);
	ret.mx2 = max(n1.mx2, n2.mx2);
	if (n1.mx != n2.mx) ret.mx2 = max(ret.mx2, min(n1.mx, n2.mx));
	ret.cnt = 0;
	if (ret.mx == n1.mx) ret.cnt += n1.cnt;
	if (ret.mx == n2.mx) ret.cnt += n2.cnt;
	return ret;
}

node tree[MAX * 4];
ll lazy[MAX * 4];
ll H[MAX];
int N;
void init(int s, int e, int loc = 1) {
	lazy[loc] = 1e18;
	if (s == e) {
		tree[loc] = node(H[s]);
		return;
	}
	int m = s + e >> 1;
	init(s, m, loc * 2);
	init(m + 1, e, loc * 2 + 1);
	tree[loc] = tree[loc * 2] + tree[loc * 2 + 1];
}

void prop(int loc) {
	for (auto c : { loc * 2, loc * 2 + 1 }) {
		ll d = tree[c].mx - lazy[loc];
		tree[c].mx = min(tree[c].mx, lazy[loc]);
		if (d < 0) d = 0;
		tree[c].sum -= 1ll * d * tree[c].cnt;
		lazy[c] = min(lazy[c], lazy[loc]);
	}
	lazy[loc] = 1e18;
}

void upd(int s, int e, int i, ll x, int loc = 1) {
	if (e < i || i < s) return;
	if (s != e) prop(loc);
	if (s == e) {
		tree[loc] = node(x);
		return;
	}
	int m = s + e >> 1;
	upd(s, m, i, x, loc * 2);
	upd(m + 1, e, i, x, loc * 2 + 1);
	tree[loc] = tree[loc * 2] + tree[loc * 2 + 1];
}
void upd(int i, ll x) { upd(1, N, i, x); }

void down(int s, int e, int l, int r, ll x, int loc = 1) {
	if (e < l || r < s) return;
	if (s != e) prop(loc);
	if (l <= s && e <= r) {
		lazy[loc] = min(lazy[loc], x);
		if (tree[loc].mx <= x) return;
		else if (tree[loc].mx2 < x) {
			tree[loc].sum -= 1ll * (tree[loc].mx - x) * tree[loc].cnt;
			tree[loc].mx = x;
			return;
		}
	}
	int m = s + e >> 1;
	down(s, m, l, r, x, loc * 2);
	down(m + 1, e, l, r, x, loc * 2 + 1);
	tree[loc] = tree[loc * 2] + tree[loc * 2 + 1];
}
void down(int l, int r, ll x) { down(1, N, l, r, x); }

node query(int s, int e, int l, int r, int loc = 1) {
	if (e < l || r < s) return node();
	if (s != e) prop(loc);
	if (l <= s && e <= r) return tree[loc];
	int m = s + e >> 1;
	return query(s, m, l, r, loc * 2) + query(m + 1, e, l, r, loc * 2 + 1);
}
node query(int l, int r) { return query(1, N, l, r); }

int mxcount(int s, int e, int l, int r, ll x, ll k, int loc = 1) {
	if (e < l || r < s) return -1;
	if (s != e) prop(loc);
	if (l <= s && e <= r) {
		if (x == tree[loc].mx) {
			if (tree[loc].cnt < k) return -1;
			if (s == e) return s;
			int m = s + e >> 1;
			int lv = 0;
			if (tree[loc * 2].mx == x) lv = tree[loc * 2].cnt;
			if (lv >= k) return mxcount(s, m, l, r, x, k, loc * 2);
			else return mxcount(m + 1, e, l, r, x, k - lv, loc * 2 + 1);
		}
		else return -1;
	}
	int m = s + e >> 1;
	int res = mxcount(s, m, l, r, x, k, loc * 2);
	if (~res) return res;
	auto q = query(s, m, l, r, loc * 2);
	int lv = 0;
	if (q.mx == x) lv = q.cnt;
	return mxcount(m + 1, e, l, r, x, k - lv, loc * 2 + 1);
}
int mxcount(int l, int r, ll x, ll k) { return mxcount(1, N, l, r, x, k); }

void initialise(int N, int Q, int h[]) {
	::N = N;
	int i;
	for (i = 1; i <= N; i++) H[i] = h[i];
	init(1, N);
}
void cut(int l, int r, int k) {
	while (k) {
		auto res = query(l, r);
		if (res.sum <= k) {
			down(l, r, 0);
			return;
		}
		if (res.mx == 0) return;
		if (res.cnt >= k) {
			int ind = mxcount(l, r, res.mx, k);
			assert(l <= ind && ind <= r);
			down(l, ind, res.mx - 1);
			break;
		}
		ll m = min(k / res.cnt, res.mx - max(0ll, res.mx2));
		down(l, r, res.mx - m);
		k -= m * res.cnt;
	}
}
void magic(int i, int x) { upd(i, x); }
long long int inspect(int l, int r) { return query(l, r).sum; }

Compilation message (stderr)

weirdtree.cpp: In function 'void init(int, int, int)':
weirdtree.cpp:49:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |  int m = s + e >> 1;
      |          ~~^~~
weirdtree.cpp: In function 'void upd(int, int, int, ll, int)':
weirdtree.cpp:73:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |  int m = s + e >> 1;
      |          ~~^~~
weirdtree.cpp: In function 'void down(int, int, int, int, ll, int)':
weirdtree.cpp:92:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |  int m = s + e >> 1;
      |          ~~^~~
weirdtree.cpp: In function 'node query(int, int, int, int, int)':
weirdtree.cpp:103:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  103 |  int m = s + e >> 1;
      |          ~~^~~
weirdtree.cpp: In function 'int mxcount(int, int, int, int, ll, ll, int)':
weirdtree.cpp:115:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  115 |    int m = s + e >> 1;
      |            ~~^~~
weirdtree.cpp:123:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  123 |  int m = 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