Submission #871290

#	Time	Username	Problem	Language	Result	Execution time	Memory
871290		TAhmed33	Weirdtree (RMI21_weirdtree)	C++17	13 / 100	35 ms	11600 KiB

weirdtree

#include <bits/stdc++.h>
#include <weirdtree.h>
using namespace std;
typedef long long ll;
#define mid ((l + r) >> 1)
#define tl (node + 1)
#define tr (node + 2 * (mid - l + 1))
const int MAXN = 8e4 + 25;
struct SegmentTree {
	int arr[MAXN]; pair <int, int> tree[2 * MAXN];
	ll sum[2 * MAXN];
	void build (int l, int r, int node) {
		if (l == r) {
			tree[node] = {arr[l], -l};
			sum[node] = arr[l];
		} else {
			build(l, mid, tl); build(mid + 1, r, tr);
			tree[node] = max(tree[tl], tree[tr]);
			sum[node] = sum[tl] + sum[tr];
		}
	}
	void update (int l, int r, int a, int b, int node) {
		if (l > a || r < a) return;
		if (l == r) {
			tree[node] = {b, -l};
			sum[node] = b;
			return;
		}
		update(l, mid, a, b, tl); update(mid + 1, r, a, b, tr);
		tree[node] = max(tree[tl], tree[tr]);
		sum[node] = sum[tl] + sum[tr];
	}
	pair <int, int> get (int l, int r, int a, int b, int node) {
		if (l > b || r < a) return {-1, 0};
		if (l >= a && r <= b) return tree[node];
		return max(get(l, mid, a, b, tl), get(mid + 1, r, a, b, tr));
	}
	ll getsum (int l, int r, int a, int b, int node) {
		if (l > b || r < a) return 0;
		if (l >= a && r <= b) return sum[node];
		return getsum(l, mid, a, b, tl) + getsum(mid + 1, r, a, b, tr);
	}
} cur;
int n;
void initialise (int N, int q, int h[]) {
	n = N;
	for (int i = 1; i <= n; i++) cur.arr[i] = h[i];
	cur.build(1, n, 1);
}
void cut (int l, int r, int z) {
	auto x = cur.get(1, n, l, r, 1);
	if (x.first == 0) return;
	x.second *= -1;
	cur.update(1, n, x.second, x.first - 1, 1);
}
void magic (int i, int x) {
	cur.update(1, n, i, x, 1);
}
long long int inspect (int l, int r) {
	return cur.getsum(1, n, l, r, 1);
}

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