Submission #588723

#	Time	Username	Problem	Language	Result	Execution time	Memory
588723		dutinmeow	Ants and Sugar (JOI22_sugar)	C++17	100 / 100	3392 ms	141824 KiB

sugar

// https://oj.uz/problem/view/JOI22_sugar

#include <bits/stdc++.h>
using namespace std;

#pragma region y_combinator

#ifndef Y_COMBINATOR_HPP
#define Y_COMBINATOR_HPP

template<class Fun>
class y_combinator_result {
	Fun fun_;
public:
	template<class T>
	explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}

	template<class ...Args>
	decltype(auto) operator()(Args &&...args) {
		return fun_(std::ref(*this), std::forward<Args>(args)...);
	}
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
	return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

#endif

#pragma endregion y_combinator

int main() {
	int Q, L;
	cin >> Q >> L;
	map<int, int> M;
	vector<int> T(Q), X(Q), A(Q);
	for (int i = 0; i < Q; i++) {
		cin >> T[i] >> X[i] >> A[i];
		M[X[i]] = 0, T[i]--;
	}

	int n = 0;
	for (auto &[k, v] : M)
		v = n++;
	
	using st_node = array<array<long long, 2>, 2>;
	using st_updt = array<long long, 2>;

	vector<st_node> st_tree(4 * n);
	vector<st_updt> st_lazy(4 * n);

	for (int i = 0; i < 4 * n; i++) {
		st_tree[i][0].fill(0);
		st_tree[i][1].fill(0);
		st_lazy[i].fill(0);
	}

	auto st_pull = [&](int t) -> void {
		st_tree[t][0].fill(LLONG_MIN);
		st_tree[t][1].fill(LLONG_MIN);
		for (int i = 0; i <= 1; i++)
			for (int j = 0; j <= 1; j++)
				for (int k = 0; k <= 1; k++)
					st_tree[t][i][k] = max(st_tree[t][i][k], st_tree[t * 2][i][j] + st_tree[t * 2 + 1][j ^ 1][k]);
	};

	auto st_push = [&](int t, int k, long long v) -> void {
		st_tree[t][k][k] += v;
		st_lazy[t][k] += v;
	};

	auto st_pushdown = [&](int t) -> void {
		for (int k : {0, 1}) {
			if (st_lazy[t][k] == 0)
				continue;
			st_push(t * 2, k, st_lazy[t][k]);
			st_push(t * 2 + 1, k, st_lazy[t][k]);
			st_lazy[t][k] = 0;
		}
	};

	auto st_update = y_combinator([&](auto st_update, int l, int r, int k, long long v, int t, int tl, int tr) -> void {
		if (r < tl || tr < l)
			return;
		if (l <= tl && tr <= r) {
			st_push(t, k, v);
			return;
		}
		st_pushdown(t);
		int tm = (tl + tr) / 2;
		st_update(l, r, k, v, t * 2, tl, tm);
		st_update(l, r, k, v, t * 2 + 1, tm + 1, tr);
		st_pull(t);
	});

	long long ants = 0;
	for (int q = 0; q < Q; q++) {
		auto [t, x, a] = tie(T[q], X[q], A[q]);
		if (t == 0)
			ants += a;
		int lb = M.lower_bound(x - L)->second, rb = M[x];
		st_update(rb, n - 1, t, a, 1, 0, n - 1);
		st_update(rb, n - 1, t ^ 1, -a, 1, 0, n - 1);
		if (lb < rb)
			st_update(lb, rb - 1, t ^ 1, -a, 1, 0, n - 1);
		cout << ants - max(st_tree[1][0][0], st_tree[1][1][0]) << '\n';
	}
}

Compilation message (stderr)

sugar.cpp:6: warning: ignoring '#pragma region y_combinator' [-Wunknown-pragmas]
    6 | #pragma region y_combinator
      | 
sugar.cpp:31: warning: ignoring '#pragma endregion y_combinator' [-Wunknown-pragmas]
   31 | #pragma endregion y_combinator
      |

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 26 / 26
• Subtask 4: 52 / 52