oj.uz

Submission #786738

# Submission time Handle Problem Language Result Execution time Memory
786738 2023-07-18T12:15:07 Z flappybird Weirdtree (RMI21_weirdtree) C++17
100 / 100
 1004 ms 54944 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 38100 KB Output is correct
2 Correct 16 ms 38100 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 38100 KB Output is correct
2 Correct 16 ms 38100 KB Output is correct
3 Correct 166 ms 42764 KB Output is correct
4 Correct 173 ms 42680 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 38036 KB Output is correct
2 Correct 19 ms 38104 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 38036 KB Output is correct
2 Correct 19 ms 38104 KB Output is correct
3 Correct 1000 ms 54852 KB Output is correct
4 Correct 994 ms 54944 KB Output is correct
5 Correct 1004 ms 54760 KB Output is correct
6 Correct 969 ms 54644 KB Output is correct
7 Correct 37 ms 42188 KB Output is correct
8 Correct 93 ms 42488 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 42188 KB Output is correct
2 Correct 93 ms 42488 KB Output is correct
3 Correct 264 ms 52420 KB Output is correct
4 Correct 236 ms 52572 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 38100 KB Output is correct
2 Correct 16 ms 38100 KB Output is correct
3 Correct 166 ms 42764 KB Output is correct
4 Correct 173 ms 42680 KB Output is correct
5 Correct 19 ms 38036 KB Output is correct
6 Correct 19 ms 38104 KB Output is correct
7 Correct 37 ms 42188 KB Output is correct
8 Correct 93 ms 42488 KB Output is correct
9 Correct 172 ms 43400 KB Output is correct
10 Correct 168 ms 43340 KB Output is correct
11 Correct 167 ms 43304 KB Output is correct
12 Correct 161 ms 43496 KB Output is correct
13 Correct 169 ms 43500 KB Output is correct

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 38100 KB Output is correct
2 Correct 16 ms 38100 KB Output is correct
3 Correct 166 ms 42764 KB Output is correct
4 Correct 173 ms 42680 KB Output is correct
5 Correct 19 ms 38036 KB Output is correct
6 Correct 19 ms 38104 KB Output is correct
7 Correct 1000 ms 54852 KB Output is correct
8 Correct 994 ms 54944 KB Output is correct
9 Correct 1004 ms 54760 KB Output is correct
10 Correct 969 ms 54644 KB Output is correct
11 Correct 264 ms 52420 KB Output is correct
12 Correct 236 ms 52572 KB Output is correct
13 Correct 172 ms 43400 KB Output is correct
14 Correct 168 ms 43340 KB Output is correct
15 Correct 167 ms 43304 KB Output is correct
16 Correct 161 ms 43496 KB Output is correct
17 Correct 169 ms 43500 KB Output is correct
18 Correct 37 ms 42188 KB Output is correct
19 Correct 93 ms 42488 KB Output is correct
20 Correct 762 ms 54064 KB Output is correct
21 Correct 786 ms 54212 KB Output is correct
22 Correct 809 ms 54188 KB Output is correct
23 Correct 795 ms 54220 KB Output is correct
24 Correct 741 ms 54096 KB Output is correct