Submission #676251

#	Time	Username	Problem	Language	Result	Execution time	Memory
676251		dutinmeow	Two Dishes (JOI19_dishes)	C++17	100 / 100	7337 ms	311880 KiB

dishes

#include <bits/stdc++.h>

template<class segment_tree_template>
class lazy_segment_tree : public segment_tree_template {
	using T = typename segment_tree_template::node_type;
	using L = typename segment_tree_template::lazy_type;
	using segment_tree_template::node_default_value;
	using segment_tree_template::lazy_default_value;
	using segment_tree_template::merge;
	using segment_tree_template::apply;

protected:
	int n;
	std::vector<T> tree;
	std::vector<L> lazy;

private:
	void pushdown(int t, int tl, int tr) {
		if (lazy[t] == lazy_default_value)
			return;
		int tm = (tl + tr) / 2;
		apply(tree[t * 2], lazy[t * 2], lazy[t], tl, tm);
		apply(tree[t * 2 + 1], lazy[t * 2 + 1], lazy[t], tm + 1, tr);
		lazy[t] = lazy_default_value;
	}

	void insert(int i, T v, int t, int tl, int tr) {
		if (tl == tr) {
			tree[t] = v;
			return;
		}
		pushdown(t, tl, tr);
		int tm = (tl + tr) / 2;
		if (i <= tm)
			insert(i, v, t * 2, tl, tm);
		else
			insert(i, v, t * 2 + 1, tm + 1, tr);
		tree[t] = merge(tree[t * 2], tree[t * 2 + 1]);
	}

	void update(int l, int r, L v, int t, int tl, int tr) {
		if (r < tl || tr < l)
			return;
		if (l <= tl && tr <= r) {
			apply(tree[t], lazy[t], v, tl, tr);
			return;
		}
		pushdown(t, tl, tr);
		int tm = (tl + tr) / 2;
		update(l, r, v, t * 2, tl, tm);
		update(l, r, v, t * 2 + 1, tm + 1, tr);
		tree[t] = merge(tree[t * 2], tree[t * 2 + 1]);
	}

	T query(int l, int r, int t, int tl, int tr) {
		if (r < tl || tr < l)
			return node_default_value;
		if (l <= tl && tr <= r)
			return tree[t];
		pushdown(t, tl, tr);
		int tm = (tl + tr) / 2;
		return merge(query(l, r, t * 2, tl, tm), query(l, r, t * 2 + 1, tm + 1, tr));
	}

public:
	lazy_segment_tree() = default;

	lazy_segment_tree(int _n) { init(_n); }

	void init(int _n) {
		n = _n;
		tree.assign(4 * n, node_default_value);
		lazy.assign(4 * n, lazy_default_value);
	}

	void insert(int i, T v) { insert(i, v, 1, 0, n - 1); }

	void update(int l, int r, L v) { update(l, r, v, 1, 0, n - 1); }

	T query(int l, int r) { return query(l, r, 1, 0, n - 1); }
};

const long long INF = 1e18;

struct range_add_range_max_segment_tree_template {
	using node_type = long long;
	using lazy_type = long long;
	const node_type node_default_value = -INF;
	const lazy_type lazy_default_value = 0;

	node_type merge(node_type a, node_type b) { return std::max(a, b); }

	void apply(node_type &a, lazy_type &b, lazy_type c, int tl, int tr) { a += c, b += c; }
};

using range_add_range_max_segment_tree = lazy_segment_tree<range_add_range_max_segment_tree_template>;

int main() {
	using namespace std;

	int N, M;
	cin >> N >> M;
	vector<long long> A(N + 1), S(N + 1), P(N + 1);
	for (int i = 1; i <= N; i++)
		cin >> A[i] >> S[i] >> P[i];
	vector<long long> B(M + 1), T(M + 1), Q(M + 1);
	for (int i = 1; i <= M; i++)
		cin >> B[i] >> T[i] >> Q[i];
	vector<long long> C(N + 1), D(M + 1);
	C[0] = D[0] = 0;
	for (int i = 1; i <= N; i++)
		C[i] = C[i - 1] + A[i];
	for (int i = 1; i <= M; i++)
		D[i] = D[i - 1] + B[i];

	long long ans = 0;
	map<pair<int, int>, long long> Z;
	for (int i = 1; i <= N; i++) {
		if (C[i] > S[i])
			continue;
		if (C[i] + D[M] <= S[i]) {
			ans += P[i];
			continue;
		}
		int ind = prev(upper_bound(D.begin(), D.end(), S[i] - C[i])) - D.begin();
		Z[{i - 1, -ind - 1}] += P[i];
	}
	for (int i = 1; i <= M; i++) {
		if (D[i] > T[i])
			continue;
		if (D[i] + C[N] <= T[i]) {
			ans += Q[i];
			continue;
		}
		int ind = prev(upper_bound(C.begin(), C.end(), T[i] - D[i])) - C.begin();
		Z[{ind, -i}] -= Q[i], ans += Q[i];
	}

	range_add_range_max_segment_tree sgt(M + 2);
	for (int i = 0; i <= M + 1; i++)
		sgt.insert(i, 0);
	for (auto [k, v] : Z) {
		int x = k.first, y = -k.second;
		auto tem = sgt.query(0, y);
		sgt.insert(y, tem);
		sgt.update(0, y - 1, v);
	}

	cout << sgt.query(0, M + 1) + ans << '\n';
}

Compilation message (stderr)

dishes.cpp: In function 'int main()':
dishes.cpp:143:7: warning: unused variable 'x' [-Wunused-variable]
  143 |   int x = k.first, y = -k.second;
      |       ^

• Subtask 1: 5 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 39 / 39
• Subtask 5: 11 / 11
• Subtask 6: 9 / 9
• Subtask 7: 17 / 17
• Subtask 8: 9 / 9