제출 #561193

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
561193		blue	Weirdtree (RMI21_weirdtree)	C++17	0 / 100	2084 ms	43604 KiB

weirdtree

#include "weirdtree.h"
#include <vector>
#include <iostream>
using namespace std;


using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;

const int mx = 300'000;
const ll INF = 1'000'000'000'000'000'000LL;

struct info
{
	int l;
	int r;

	ll mxv;
	int mxct;
	ll mxv2;

	ll sm;

	info()
	{
		;
	}

	info(int i, ll v)
	{
		l = r = i;

		mxv = v;

		mxct = 1;
		mxv2 = -1;

		sm = v;
	}
};

void combine(info& res, const info& a, const info& b)
{
	// res.l = a.l;
	// res.r = b.r; //if slow, get rid of this part

	res.mxv = max(a.mxv, b.mxv);
	res.mxct = (a.mxv == res.mxv ? a.mxct : 0) + (b.mxv == res.mxv ? b.mxct : 0);

	res.mxv2 = -INF;
	for(ll z : {a.mxv, b.mxv, a.mxv2, b.mxv2})
		if(z < res.mxv)
			res.mxv2 = max(res.mxv2, z);

	res.sm = a.sm + b.sm;
}

info get_combine(const info& a, const info& b)
{
	info res;
	combine(res, a, b);
	res.l = a.l;
	res.r = b.r;
	return res;
}


int N, Q;
vi h;

struct segtree
{
	vector<info> v = vector<info>(mx<<2);

	void build(int i, int l, int r)
	{
		if(l == r)
			v[i] = info(l, h[l]);
		else
		{
			build(2*i, l, (l+r)/2);
			build(2*i+1, (l+r)/2+1, r);
			combine(v[i], v[2*i], v[2*i+1]);
			v[i].l = l;
			v[i].r = r;
		}
	}

	void maxlim(int i, int L, int R, ll z)
	{
		if(R < v[i].l || v[i].r < L) return;
		else if(L <= v[i].l && v[i].r <= R)
		{
			if(v[i].mxv2 < z && z < v[i].mxv)
			{
				v[i].sm += (z - v[i].mxv) * v[i].mxct;
				v[i].mxv = v[i].sm;
			}
			else
			{
				if(v[i].l != v[i].r)
				{
					maxlim(2*i, 0, N-1, v[i].mxv);
					maxlim(2*i+1, 0, N-1, v[i].mxv);
					maxlim(2*i, L, R, z);
					maxlim(2*i+1, L, R, z);

					combine(v[i], v[2*i], v[2*i+1]);
				}
			}
		}
		else
		{
			maxlim(2*i, 0, N-1, v[i].mxv);
			maxlim(2*i+1, 0, N-1, v[i].mxv);
			maxlim(2*i, L, R, z);
			maxlim(2*i+1, L, R, z);

			combine(v[i], v[2*i], v[2*i+1]);
		}
	}

	ll rangesum(int i, int L, int R)
	{
		if(R < v[i].l || v[i].r < L) return 0;
		else if(L <= v[i].l && v[i].r <= R)
		{
			return v[i].sm;
		}
		else
		{
			maxlim(2*i, 0, N-1, v[i].mxv);
			maxlim(2*i+1, 0, N-1, v[i].mxv);
			return rangesum(2*i, L, R) + rangesum(2*i+1, L, R);
		}
	}

	void magic(int i, int p, ll x)
	{
		if(v[i].l == v[i].r)
		{
			v[i] = info(p, x);
		}
		else 
		{
			maxlim(2*i, 0, N-1, v[i].mxv);
			maxlim(2*i+1, 0, N-1, v[i].mxv);

			if(p <= (v[i].l + v[i].r) / 2)
			{
				magic(2*i, p, x);
			}
			else
			{
				magic(2*i+1, p, x);
			}

			combine(v[i], v[2*i], v[2*i+1]);
		}
	}

	ll rangemax(int i, int L, int R)
	{
		if(R < v[i].l || v[i].r < L)
			return -INF;
		else if(L <= v[i].l && v[i].r <= R)
			return v[i].mxv;
		else
		{
			maxlim(2*i, 0, N-1, v[i].mxv);
			maxlim(2*i+1, 0, N-1, v[i].mxv);
			return max(rangemax(2*i, L, R), rangemax(2*i+1, L, R));
		}
	}

	info scombine(int i, int L, int R)
	{
		if(L <= v[i].l && v[i].r <= R)
			return v[i];

		maxlim(2*i, 0, N-1, v[i].mxv);
		maxlim(2*i+1, 0, N-1, v[i].mxv);

		if(R <= (v[i].l + v[i].r)/2)
			return scombine(2*i, L, R);
		else if(L >= (v[i].l + v[i].r)/2 + 1)
			return scombine(2*i+1, L, R);
		else 
			return get_combine(scombine(2*i, L, R), scombine(2*i+1, L, R));
	}

	ll dec(int i, int L, int R, ll c)
	{
		if(R < v[i].l || v[i].r < L)
			return 0;

		if(v[i].mxv <= 0)
			return 0;

		if(c <= 0)
			return 0;

		else if(L <= v[i].l && v[i].r <= R)
		{
			if(v[i].mxct <= c)
			{
				maxlim(i, L, R, v[i].mxv - 1);
				return v[i].mxct;
			}
			else
			{
				maxlim(2*i, 0, N-1, v[i].mxv);
				maxlim(2*i+1, 0, N-1, v[i].mxv);

				ll l_used = dec(2*i, L, R, c);
				c -= l_used;

				ll r_used = dec(2*i+1, L, R, c);

				combine(v[i], v[2*i], v[2*i+1]);

				return l_used + r_used;
			}
		}
		else
		{
			maxlim(2*i, 0, N-1, v[i].mxv);
			maxlim(2*i+1, 0, N-1, v[i].mxv);

			ll l_used = dec(2*i, L, R, c);
			c -= l_used;

			ll r_used = dec(2*i+1, L, R, c);

			combine(v[i], v[2*i], v[2*i+1]);

			return l_used + r_used;
		}
	}


};

segtree S;




void initialise(int N_, int Q_, int h_[]) {
	N = N_;
	Q = Q_;
	h = vi(N);
	for(int i = 0; i < N; i++)
		h[i] = h_[i+1];

	S.build(1, 0, N-1);

	// for(int i = 0; i < N; i++) cerr << S.rangemax(1, i, i) << ' ';
	// 	cerr << '\n';
}



void cut(int l, int r, int k) 
{
	l--;
	r--;
	ll prevk = -1;
	while(k >= 0)
	{
		// cerr << "k = " << k << '\n';
		info z = S.scombine(1, l, r);

		if(z.mxv <= 0) break;

		z.mxv2 = max(z.mxv2, 0LL);

		ll req = (z.mxv - z.mxv2) * z.mxct;

		if(req <= k)
		{
			S.maxlim(1, l, r, z.mxv2);
			k -= req;
		}
		else
		{
			ll fullturns = k / z.mxct;

			if(fullturns >= 1)
				S.maxlim(1, l, r, z.mxv - fullturns);

			k -= fullturns * z.mxct;

			if(k >= 1)
				S.dec(1, l, r, k);
			break;
		}	
		if(k == prevk)
			break;
		prevk = k;
	}

	// cerr << "! ";

	// for(int i = 0; i < N; i++) cerr << S.rangemax(1, i, i) << ' ';
	// 	cerr << '\n';
}



void magic(int i, int x) 
{
	i--;
	S.magic(1, i, x);

	// cerr << "! ";

	// for(int i = 0; i < N; i++) cerr << S.rangemax(1, i, i) << ' ';
	// 	cerr << '\n';
}




long long int inspect(int l, int r) {
	l--;
	r--;
	return S.rangesum(1, l, r);
}

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