제출 #1133079

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1133079		NK_	Weirdtree (RMI21_weirdtree)	C++20	15 / 100	1629 ms	31948 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;

	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); 

	// cout << l << " " << r << " -> " << k << " ===> " << L << " " << R << endl;
	if (seg[x].mx < v || k == 0) return -1;
	// cout << seg[x].mx << " " << seg[x].amt << endl;

	if (L == R && seg[x].amt >= k) return L;

	if (r < L || R < l) return -1;


	if (l <= L && R <= r && seg[x].amt < k) {
		k -= seg[x].amt; return -1;
	}

	int M = (L + R) / 2;
	int res = find(l, r, v, k, 2 * x, L, M);
	if (res == -1) res = find(l, r, v, k, 2 * x + 1, M + 1, R);
	return 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) {
		T res = qry(l, r);
		int bnd = find(l, r, res.mx, k);
		// cout << "BND: " << bnd << endl;
		upd(l, bnd, res.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: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 19
• Subtask 5: 10 / 10
• Subtask 6: 0 / 21
• Subtask 7: 0 / 29