제출 #1121144

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1121144		aykhn	Weirdtree (RMI21_weirdtree)	C++17	23 / 100	2060 ms	38216 KiB

weirdtree

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

using namespace std;

#define inf 0x3F3F3F3F

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

const long long MXN = 3e5 + 5;

long long 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(long long l, long long r, long long x)
{
	if (l == r)
	{
		st[x] = {arr[l], -inf, 1, arr[l]};
		return;
	}
	long long 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(long long x, long long val)
{
	if (st[x].mx1 > val)
	{
		st[x].s -= (st[x].mx1 - val) * st[x].cnt;
		st[x].mx1 = val;
	}
}
void upd(long long l, long long r, long long x, long long lx, long long rx, long long 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)
	{
		long long 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(long long l, long long r, long long x, long long 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;
	}
	long long 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]);
}
long long gets(long long l, long long r, long long x, long long lx, long long 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;
	long long mid = (l + r) >> 1;
	return gets(l, mid, 2*x, lx, rx) + gets(mid + 1, r, 2*x + 1, lx, rx);
}
DATA get(long long l, long long r, long long x, long long lx, long long 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];
	long long mid = (l + r) >> 1;
	return combine(get(l, mid, 2*x, lx, rx), get(mid + 1, r, 2*x + 1, lx, rx));
}
array<long long, 2> findkthval(long long l, long long r, long long x, long long lx, long long rx, long long k, long long 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};
	long long mid = (l + r) >> 1;
	array<long long, 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);
}

void initialise(int N, int Q, int h[]) 
{
	for (long long i = 1; i <= N; i++) arr[i] = h[i];
	n = N;
	st[0] = {inf, inf, 0, 0};
	build(1, n, 1);
}
void cut(int l, int r, int K) 
{
	long long k = K;
	while (1)
	{
		DATA x = get(1, n, 1, l, r);
		if (x.mx1 == 0) return;
		long long lw = max(0LL, x.mx2);
		if ((x.mx1 - lw) * x.cnt > k) 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;
	array<long long, 2> q = findkthval(1, n, 1, l, r, (k - 1) % x.cnt + 1, x.mx1);
	while (q[0] < l || r < q[0]);
	upd(1, n, 1, l, q[0], max(0LL, x.mx1 - ((k + x.cnt - 1) / x.cnt)));
	upd(1, n, 1, q[0] + 1, r, max(0LL, x.mx1 - (k / x.cnt)));
}
void magic(int i, int x) 
{
	arr[i] = x;
	make(1, n, 1, i);
}
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: 10 / 10
• Subtask 6: 0 / 21
• Subtask 7: 0 / 29