Submission #1121098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121098		vjudge1	Weirdtree (RMI21_weirdtree)	C++17	13 / 100	93 ms	17368 KiB

weirdtree

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

using namespace std;

#define int long long
#define inf 0x3F3F3F3F

struct DATA
{
	long long mx1 = -inf, mx2 = -inf, cnt = 0, s = 0;
};

const int MXN = 80000 + 5;

int n;
long long arr[MXN];
DATA st[MXN << 2];

DATA combine(DATA x, DATA y)
{
	if (x.mx1 == y.mx1) return {x.mx1, max(x.mx2, y.mx2), x.cnt + y.cnt, x.s + y.s};
	else if (x.mx1 > y.mx1) return {x.mx1, max(x.mx2, y.mx1), x.cnt, x.s + y.s};
	else return {y.mx1, max(x.mx1, y.mx2), y.cnt, x.s + y.s};
}

void build(int l, int r, int x)
{
	if (l == r)
	{
		st[x] = {arr[l], -inf, 1, arr[l]};
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, 2*x);
	build(mid + 1, r, 2*x + 1);
	st[x] = combine(st[2*x], st[2*x + 1]);
}
void relax(int x, int val)
{
	if (st[x].mx1 > val)
	{
		st[x].s -= (st[x].mx1 - val) * st[x].cnt;
		st[x].mx1 = val;
	}
}
void upd(int l, int r, int x, int lx, int rx, int val)
{
	if (lx > rx) return;
	relax(x, st[x / 2].mx1);
	if (l > rx || r < lx) return;
	if (st[x].mx1 <= val) return;
	if (!(l >= lx && r <= rx) || st[x].mx2 >= val)
	{
		int mid = (l + r) >> 1;
		upd(l, mid, 2*x, lx, rx, val);
		upd(mid + 1, r, 2*x + 1, lx, rx, val);
		st[x] = combine(st[2*x], st[2*x + 1]);
	}
	else relax(x, val);
}
void make(int l, int r, int x, int ind)
{
	relax(x, st[x / 2].mx1);
	if (!(l <= ind && ind <= r)) return;
	if (l == r) 
	{
		st[x] = {arr[l], -inf, 1, arr[l]};
		return;
	}
	int mid = (l + r) >> 1;
	make(l, mid, 2*x, ind);
	make(mid + 1, r, 2*x + 1, ind);
	st[x] = combine(st[2*x], st[2*x + 1]);
}
int gets(int l, int r, int x, int lx, int rx)
{
	if (lx > rx) return 0;
	if (l > rx || r < lx) return 0;
	relax(x, st[x / 2].mx1);
	if (l >= lx && r <= rx) return st[x].s;
	int mid = (l + r) >> 1;
	return gets(l, mid, 2*x, lx, rx) + gets(mid + 1, r, 2*x + 1, lx, rx);
}
DATA get(int l, int r, int x, int lx, int rx)
{
	if (lx > rx) return {-inf, -inf, 0, 0};
	if (l > rx || r < lx) return {-inf, -inf, 0, 0};
	relax(x, st[x / 2].mx1);
	if (l >= lx && r <= rx) return st[x];
	int mid = (l + r) >> 1;
	return combine(get(l, mid, 2*x, lx, rx), get(mid + 1, r, 2*x + 1, lx, rx));
}
array<int, 2> findkthval(int l, int r, int x, int lx, int rx, int k, int val)
{
	if (lx > rx) return {-1, 0};
	if (l > rx || r < lx) return {-1, 0};
	relax(x, st[x / 2].mx1);
	if (l >= lx && r <= rx && (st[x].mx1 != val || st[x].cnt < k)) return {-1, 1LL * (st[x].mx1 == val) * st[x].cnt};
	if (l == r) return {l, 1LL * (st[x].mx1 == val) * st[x].cnt};
	int mid = (l + r) >> 1;
	array<int, 2> A = findkthval(l, mid, 2*x, lx, rx, k, val);
	if (A[0] != -1) return A;
	return findkthval(mid + 1, r, 2*x + 1, lx, rx, k - A[1], val);
}

#undef int

void initialise(int N, int Q, int h[]) 
{
	#define int long long
	for (int i = 1; i <= N; i++) arr[i] = h[i];
	n = N;
	st[0] = {inf, inf, 0, 0};
	build(1, n, 1);
	#undef int
}
void cut(int l, int r, int k) 
{
	#define int long long
	while (1)
	{
		DATA x = get(1, n, 1, l, r);
		if (x.mx1 == 0) break;
		int lw = max(0LL, x.mx2);
		while (!x.cnt);
		if (x.mx1 - (k / x.cnt) > lw) break;
		upd(1, n, 1, l, r, lw);
		k -= (x.mx1 - lw) * x.cnt;
	}
	if (!k) return;
	DATA x = get(1, n, 1, l, r);
	if (x.mx1 == 0) return;
	while (!x.cnt);
	array<int, 2> q = findkthval(1, n, 1, l, r, (k - 1) % x.cnt + 1, x.mx1);
	while (q[0] < l);
	while (!x.cnt);
	upd(1, n, 1, l, q[0], x.mx1 - ((k + x.cnt - 1) / x.cnt));
	upd(1, n, 1, q[0] + 1, r, x.mx1 - (k / x.cnt));
	#undef int
}
void magic(int i, int x) 
{
	#define int long long
	arr[i] = x;
	make(1, n, 1, i);
	#undef int
}
long long int inspect(int l, int r) 
{
	return gets(1, n, 1, l, r);
}

• 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