Submission #597803

#	Time	Username	Problem	Language	Result	Execution time	Memory
597803		pedroslrey	Weirdtree (RMI21_weirdtree)	C++17	13 / 100	2071 ms	30160 KiB

weirdtree

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

using namespace std;
using lli = long long;

struct node {
	int mx, idx;
	lli sum;

	node (int x = 0, int i = 0, lli s = 0) : mx {x}, idx {i}, sum {s} { }

	node operator+(node other) {
		if (mx > other.mx) return node(mx, idx, sum + other.sum);
		if (mx < other.mx) return node(other.mx, other.idx, sum + other.sum);
		return node(mx, min(idx, other.idx), sum + other.sum);
	}
};

const int MAXN = 3e5 + 10;

int n;
int xs[MAXN];
node seg[4*MAXN];

node query(int pos, int ini, int fim, int l, int r) {
	if (l <= ini && fim <= r) return seg[pos];
	if (r < ini || fim < l) return node();

	int m = (ini + fim)/2;
	return query(2*pos, ini, m, l, r) + query(2*pos + 1, m + 1, fim, l, r);
}

void update(int pos, int ini, int fim, int idx, int x, bool b) {
	if (ini == fim) {
		if (b) { seg[pos].mx = x; seg[pos].sum = x; }
		else if (seg[pos].mx > 0) { seg[pos].mx += x; seg[pos].sum += x; }
		return;
	}

	int m = (ini + fim)/2;
	if (idx <= m) update(2*pos, ini, m, idx, x, b);
	else update(2*pos + 1, m + 1, fim, idx, x, b);

	seg[pos] = seg[2*pos] + seg[2*pos + 1];
}

void build(int pos, int ini, int fim) {
	if (ini == fim) {
		seg[pos] = node(xs[ini], ini, xs[ini]);
		return;
	}

	int m = (ini + fim)/2;
	build(2*pos, ini, m);
	build(2*pos + 1, m + 1, fim);

	seg[pos] = seg[2*pos] + seg[2*pos + 1];
}

void initialise(int sz, int q, int hs[]) {
	for (int i = 1; i <= sz; ++i)
		xs[i] = hs[i];

	build(1, 1, sz);
	n = sz;
}

void cut(int l, int r, int k) {
	for (int j = 0; j < k; ++j) {
		int i = query(1, 1, n, l, r).idx;
		update(1, 1, n, i, -1, false);
	}
}

void magic(int i, int x) {
	update(1, 1, n, i, x, true);
}

lli inspect(int l, int r) {
	return query(1, 1, n, l, r).sum;
}

• 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