Submission #570261

#	Time	Username	Problem	Language	Result	Execution time	Memory
570261		dutinmeow	Food Court (JOI21_foodcourt)	C++17	100 / 100	528 ms	64160 KiB

foodcourt

#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() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	int N, M, Q;
	cin >> N >> M >> Q;

	vector<int> typ(Q), grp(Q);
	vector<long long> num(Q);
	vector<vector<int>> qlb(N), qmb(N), qrb(N);
	for (int i = 0; i < Q; i++) {
		int t;
		cin >> t;
		typ[i] = t;
		if (t == 1) {
			int l, r, c;
			long long k;
			cin >> l >> r >> c >> k;
			l--, r--;
			qlb[l].push_back(i);
			qrb[r].push_back(i);
			grp[i] = c;
			num[i] = k;
		} else if (t == 2) {
			int l, r;
			long long k;
			cin >> l >> r >> k;
			l--, r--;
			qlb[l].push_back(i);
			qrb[r].push_back(i);
			num[i] = k;
		} else if (t == 3) {
			int a;
			long long b;
			cin >> a >> b;
			a--;
			qmb[a].push_back(i);
			num[i] = b;
		}
	}

	vector<long long> suf_sum(4 * Q, 0), all_sum(4 * Q, 0), add_sum(4 * Q, 0);

	// updates index i in segment tree to v
	auto seg_update = y_combinator([&](auto seg_update, int i, int v, int t, int tl, int tr) -> void {
		if (tl == tr) {
			assert(tl == i);
			all_sum[t] = v;
			suf_sum[t] = add_sum[t] = max(v, 0);
			return;
		}
		int tm = (tl + tr) / 2;
		if (i <= tm)
			seg_update(i, v, t * 2, tl, tm);
		else 
			seg_update(i, v, t * 2 + 1, tm + 1, tr);
		suf_sum[t] = max(suf_sum[t * 2] + all_sum[t * 2 + 1], suf_sum[t * 2 + 1]);
		all_sum[t] = all_sum[t * 2] + all_sum[t * 2 + 1];
		add_sum[t] = add_sum[t * 2] + add_sum[t * 2 + 1];
	});

	// finds maximum suffix sum that ends at index i (number of customers)
	auto seg_max_suf = y_combinator([&](auto seg_max_suf, int i, int t, int tl, int tr) -> pair<long long, long long> {
		if (i < tl)
			return make_pair(0, 0);
		if (tr <= i)
			return make_pair(suf_sum[t], all_sum[t]);
		int tm = (tl + tr) / 2;
		auto [lsuf, lall] = seg_max_suf(i, t * 2, tl, tm);
		auto [rsuf, rall] = seg_max_suf(i, t * 2 + 1, tm + 1, tr);
		return make_pair(max(lsuf + rall, rsuf), lall + rall);
	});

	// finds sum of first i queries that are positive
	auto seg_add_sum = y_combinator([&](auto seg_add_sum, int i, int t, int tl, int tr) -> long long {
		if (i < tl)
			return 0;
		if (tr <= i)
			return add_sum[t];
		int tm = (tl + tr) / 2;
		return seg_add_sum(i, t * 2, tl, tm) + seg_add_sum(i, t * 2 + 1, tm + 1, tr);
	});

	// find index of query where kth customer arrived
	auto seg_find_index = y_combinator([&](auto seg_find_index, long long k, int t, int tl, int tr) -> int {
		if (tl == tr)
			return tl;
		int tm = (tl + tr) / 2;
		if (k <= add_sum[t * 2])
			return seg_find_index(k, t * 2, tl, tm);
		else 
			return seg_find_index(k - add_sum[t * 2], t * 2 + 1, tm + 1, tr);
	});

	vector<int> ans(Q);
	for (int i = 0; i < N; i++) {
		for (int q : qlb[i]) {
			if (typ[q] == 1)
				seg_update(q, num[q], 1, 0, Q - 1);
			else if (typ[q] == 2)
				seg_update(q, -num[q], 1, 0, Q - 1);
		}
		for (int q : qmb[i]) {
			long long b = num[q], f = seg_max_suf(q, 1, 0, Q - 1).first;
			if (f < b) {
				ans[q] = 0;
				continue;
			}
			long long d = f - b, s = seg_add_sum(q, 1, 0, Q - 1);
			int a = seg_find_index(s - d, 1, 0, Q - 1);
			ans[q] = grp[a];
		}
		for (int q : qrb[i]) {
			seg_update(q, 0, 1, 0, Q - 1);
		}
	}

	for (int i = 0; i < Q; i++)
		if (typ[i] == 3)
			cout << ans[i] << '\n';
}

Compilation message (stderr)

foodcourt.cpp:4: warning: ignoring '#pragma region y_combinator' [-Wunknown-pragmas]
    4 | #pragma region y_combinator
      | 
foodcourt.cpp:29: warning: ignoring '#pragma endregion y_combinator' [-Wunknown-pragmas]
   29 | #pragma endregion y_combinator
      |

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 21 / 21
• Subtask 5: 15 / 15
• Subtask 6: 13 / 13
• Subtask 7: 26 / 26
• Subtask 8: 11 / 11