Submission #1133094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133094		NK_	Weirdtree (RMI21_weirdtree)	C++20	52 / 100	2093 ms	32604 KiB

weirdtree

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
#include "weirdtree.h"

using namespace std;


#define nl '\n'

template<class T> using V = vector<T>;
using ll = long long;
const int nax = (1 << 19);
const int INF = 1e9 + 10;

struct T {
	int mx = -1, amt = 0;
	int mx2 = -1, amt2 = 0;
	ll sum = 0;
};

T seg[2 * nax];
int lzy[2 * nax]; // value that mx is reduced to


T comb(T a, T b) {
	T c;

	if (a.mx == b.mx) {
		c.mx = a.mx; c.amt = a.amt + b.amt;
		c.mx2 = max(a.mx2, b.mx2);
		c.amt2 = (c.mx2 == a.mx2 ? a.amt2 : 0) + (c.mx2 == b.mx2 ? b.amt2 : 0);
	} else if (a.mx > b.mx) {
		c.mx = a.mx; c.amt = a.amt;
		c.mx2 = max(a.mx2, b.mx);
		c.amt2 = (c.mx2 == a.mx2 ? a.amt2 : 0) + (c.mx2 == b.mx ? b.amt : 0);
	} else {
		c.mx = b.mx; c.amt = b.amt;
		c.mx2 = max(a.mx, b.mx2);
		c.amt2 = (c.mx2 == a.mx ? a.amt : 0) + (c.mx2 == b.mx2 ? b.amt2 : 0);
	}

	// map<int, int> C; 
	// C[a.mx] += a.amt; C[a.mx2] += a.amt2;
	// C[b.mx] += b.amt; C[b.mx2] += b.amt2;

	// tie(c.mx, c.amt) = *rbegin(C); C.erase(prev(end(C)));
	// tie(c.mx2, c.amt2) = *rbegin(C); C.erase(prev(end(C)));

	c.sum = a.sum + b.sum;

	return c;
}

void pull(int x) { seg[x] = comb(seg[2 * x], seg[2 * x + 1]); }

void push(int x, int L, int R) {
	if (lzy[x] < seg[x].mx) {
		seg[x].sum -= (seg[x].mx - lzy[x]) * 1LL * seg[x].amt;
		seg[x].mx = lzy[x];

		if (L != R) for(int i = 0; i < 2; i++) lzy[2 * x + i] = lzy[x];
	}

	lzy[x] = INF;
}

void upd(int l, int r, int v, int x = 1, int L = 0, int R = nax - 1) {
	push(x, L, R); if (r < L || R < l || seg[x].mx <= v) return;

	// cout << l << " " << r << " -> " << L << " " << R << " -> " << v << endl;
	// cout << seg[x].mx << " " << seg[x].mx2 << endl;

	if (l <= L && R <= r && seg[x].mx2 < v) {
		// cout << "LZY" << endl;
		lzy[x] = v; push(x, L, R);
		return;
	}

	int M = (L + R) / 2;
	upd(l, r, v, 2 * x, L, M);
	upd(l, r, v, 2 * x + 1, M + 1, R);
	pull(x);
}

int find(int l, int r, int v, int &k, int x = 1, int L = 0, int R = nax - 1) {
	push(x, L, R); if (r < L || R < l || seg[x].mx < v || !k) return -1;

	if (l <= L && R <= r) { // in the range (mx <= v, mx !< v => mx == v)
		cout << L << " " << R << " " << seg[x].mx << " " << seg[x].amt << " " << v << " -> " << k << endl;

		if (seg[x].amt < k) {
			k -= seg[x].amt;
			return -1;
		}

		if (L == R) {
			cout << "FOUND: " << L << " " << seg[x].mx << " " << seg[x].amt << " " << v << " -> " << k << endl;
			k = 0;
			return L;
		}

		// otherwise continue search
	}

	int M = (L + R) / 2;
	int res = find(l, r, v, k, 2 * x, L, M);
	int res2 = find(l, r, v, k, 2 * x + 1, M + 1, R);
	return (res == -1 ? res2 : res);
}

void updx(int p, int v, int x = 1, int L = 0, int R = nax - 1) {
	push(x, L, R); if (p < L || R < p) return;

	if (L == R) {
		// cout << L << " -> " << v << endl;
		seg[x] = T{v, 1, -1, 0, v};
		return;
	}
	
	int M = (L + R) / 2;
	
	updx(p, v, 2 * x, L, M);
	updx(p, v, 2 * x + 1, M + 1, R);
	pull(x);
}

T qry(int l, int r, int x = 1, int L = 0, int R = nax - 1) {
	push(x, L, R); if (r < L || R < l) return T();
	// cout << x << " " << L << " " << R << " --> " << seg[x].mx << " " << seg[x].amt << " " << seg[x].sum << endl;
	if (l <= L && R <= r) return seg[x];
	int M = (L + R) / 2;
	return comb(qry(l, r, 2 * x, L, M), qry(l, r, 2 * x + 1, M + 1, R));
}

void initialise(int N, int Q, int h[]) {
	for(int i = 0; i < 2 * nax; i++) seg[i] = T(), lzy[i] = INF;
	for(int i = 0; i < N; i++) updx(i, h[i + 1]);
	// cout << "INIT COMPLETE" << endl;
}

void cut(int l, int r, int k) {
	--l, --r;
	// cout << "CUT: " << l << " " << r << " " << k << endl;
	while(1) {
		T res = qry(l, r);
		if (res.mx == 0) return;
		res.mx2 = max(res.mx2, 0);
		// cout << res.mx << " " << res.amt << endl;
		ll need = (res.mx - res.mx2) * 1LL * res.amt;
		// cout << need << endl;

		if (need <= k) {
			upd(l, r, res.mx2);
			k -= need;
		} else {
			int dec = k / res.amt;
			upd(l, r, res.mx - dec);
			k %= res.amt;
			break;
		}	
	}

	// cout << "LEFT: " << k << endl;
		
	if (k) {
		// assert(false);
		T all = qry(l, r);

		int lo = l, hi = r;
		while(lo < hi) {
			int mid = (lo + hi) / 2;
			T res = qry(l, mid);
			int cnt = (res.mx == all.mx ? res.amt : 0);
			if (cnt >= k) hi = mid;
			else lo = mid + 1;
		}

		int bnd = lo;
		// assert(qry(l, bnd).amt == k);
		// int bnd = find(l, r, all.mx, k);
		// cout << "BND: " << bnd << " <--> " << lo << endl;
		upd(l, bnd, all.mx - 1);
	}

// 
	// cout << "DONE" << endl;
}

void magic(int i, int x) {
	--i;
	// cout << "MAGIC: " << i << " " << x << endl;
	updx(i, x);
	// cout << "DONE" << endl;
}

long long inspect(int l, int r) {
	--l, --r;
	// cout << "INSPECT: " << l << " " << r << endl;
	return qry(l, r).sum;
}


// g++-13 -DEVAL -O2 -std=c++17 grader.cpp A.cpp -o G
	

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