Submission #645479

#	Time	Username	Problem	Language	Result	Execution time	Memory
645479		Vanilla	Weirdtree (RMI21_weirdtree)	C++17	13 / 100	81 ms	13356 KiB

weirdtree

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

const int maxn = 8e4;
struct node {
	int64 v = 0;
	int64 mx = -1;
	int64 mxpos = 0;

	const node operator+ (const node& oth) const {
		node nw;
		nw.v = v + oth.v;
		if (mx >= oth.mx) {
			nw.mx = mx;
			nw.mxpos = mxpos;
		}
		else {
			nw.mx = oth.mx;
			nw.mxpos = oth.mxpos;
		}
		return nw;
	}
} sgt [4 * maxn];

node upd (int x, int l, int r, int pos, int64 v) {
	if (l > pos || r < pos) return sgt[x];
	if (l == pos && r == pos) {
		sgt[x].v = sgt[x].mx = v;
		sgt[x].mxpos = pos;
		return sgt[x];
	}
	int mid = (l + r) / 2;
	return sgt[x] = upd(x * 2, l, mid, pos, v) + upd(x * 2 + 1, mid + 1, r, pos, v);
}

node query (int x, int l, int r, int il, int ir) {
	if (l > ir || r < il) return node();
	if (il <= l && r <= ir) return sgt[x];
	int mid = (l + r) / 2;
	return query(x * 2, l, mid, il, ir) + query(x * 2 + 1, mid + 1, r, il, ir);
}

int n;

void initialise(int N, int Q, int h[]) {
	n = N;
	for (int i = 1; i <= N; i++){
		upd(1, 1, N, i, h[i]);
	}
}
void cut(int l, int r, int k) {
	node q = query(1, 1, n, l, r);
	if (q.mx) {
		upd(1, 1, n, q.mxpos, q.mx - 1);
	}
}
void magic(int i, int x) {
	upd(1, 1, n, i, x);
}
int64 inspect(int l, int r) {
	return query(1, 1, n, l, r).v;
}

• 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