oj.uz

Submission #588723

# Submission time Handle Problem Language Result Execution time Memory
588723 2022-07-03T23:50:09 Z dutinmeow Ants and Sugar (JOI22_sugar) C++17
100 / 100
 3392 ms 141824 KB 
// 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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 6 ms 596 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 436 KB Output is correct
10 Correct 7 ms 1120 KB Output is correct
11 Correct 8 ms 1108 KB Output is correct
12 Correct 8 ms 1084 KB Output is correct
13 Correct 8 ms 1144 KB Output is correct
14 Correct 7 ms 1080 KB Output is correct
15 Correct 8 ms 1120 KB Output is correct
16 Correct 9 ms 1136 KB Output is correct
17 Correct 9 ms 1108 KB Output is correct
18 Correct 9 ms 1108 KB Output is correct
19 Correct 8 ms 1080 KB Output is correct
20 Correct 9 ms 1116 KB Output is correct
21 Correct 9 ms 1152 KB Output is correct
22 Correct 14 ms 1112 KB Output is correct
23 Correct 10 ms 1112 KB Output is correct
24 Correct 9 ms 1064 KB Output is correct
25 Correct 10 ms 1108 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1545 ms 70064 KB Output is correct
5 Correct 754 ms 67280 KB Output is correct
6 Correct 1888 ms 81856 KB Output is correct
7 Correct 754 ms 67876 KB Output is correct
8 Correct 2316 ms 96724 KB Output is correct
9 Correct 1611 ms 140528 KB Output is correct
10 Correct 2363 ms 96920 KB Output is correct
11 Correct 1598 ms 140472 KB Output is correct
12 Correct 679 ms 61232 KB Output is correct
13 Correct 961 ms 84232 KB Output is correct
14 Correct 1619 ms 137100 KB Output is correct
15 Correct 1623 ms 137052 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 694 ms 61156 KB Output is correct
3 Correct 980 ms 84312 KB Output is correct
4 Correct 1605 ms 137156 KB Output is correct
5 Correct 1592 ms 137280 KB Output is correct
6 Correct 1707 ms 80680 KB Output is correct
7 Correct 93 ms 8708 KB Output is correct
8 Correct 798 ms 47008 KB Output is correct
9 Correct 1301 ms 65052 KB Output is correct
10 Correct 2576 ms 138380 KB Output is correct
11 Correct 2675 ms 138460 KB Output is correct
12 Correct 2604 ms 138296 KB Output is correct
13 Correct 2486 ms 138308 KB Output is correct
14 Correct 2560 ms 138628 KB Output is correct
15 Correct 2260 ms 138176 KB Output is correct
16 Correct 2486 ms 138368 KB Output is correct
17 Correct 3004 ms 138524 KB Output is correct
18 Correct 3139 ms 138480 KB Output is correct
19 Correct 3212 ms 138548 KB Output is correct
20 Correct 3137 ms 138480 KB Output is correct
21 Correct 3392 ms 138676 KB Output is correct
22 Correct 3320 ms 138416 KB Output is correct
23 Correct 3281 ms 138404 KB Output is correct
24 Correct 2656 ms 138400 KB Output is correct
25 Correct 2906 ms 138572 KB Output is correct

Subtask #4
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 6 ms 596 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 436 KB Output is correct
10 Correct 7 ms 1120 KB Output is correct
11 Correct 8 ms 1108 KB Output is correct
12 Correct 8 ms 1084 KB Output is correct
13 Correct 8 ms 1144 KB Output is correct
14 Correct 7 ms 1080 KB Output is correct
15 Correct 8 ms 1120 KB Output is correct
16 Correct 9 ms 1136 KB Output is correct
17 Correct 9 ms 1108 KB Output is correct
18 Correct 9 ms 1108 KB Output is correct
19 Correct 8 ms 1080 KB Output is correct
20 Correct 9 ms 1116 KB Output is correct
21 Correct 9 ms 1152 KB Output is correct
22 Correct 14 ms 1112 KB Output is correct
23 Correct 10 ms 1112 KB Output is correct
24 Correct 9 ms 1064 KB Output is correct
25 Correct 10 ms 1108 KB Output is correct
26 Correct 1 ms 300 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 0 ms 212 KB Output is correct
29 Correct 1545 ms 70064 KB Output is correct
30 Correct 754 ms 67280 KB Output is correct
31 Correct 1888 ms 81856 KB Output is correct
32 Correct 754 ms 67876 KB Output is correct
33 Correct 2316 ms 96724 KB Output is correct
34 Correct 1611 ms 140528 KB Output is correct
35 Correct 2363 ms 96920 KB Output is correct
36 Correct 1598 ms 140472 KB Output is correct
37 Correct 679 ms 61232 KB Output is correct
38 Correct 961 ms 84232 KB Output is correct
39 Correct 1619 ms 137100 KB Output is correct
40 Correct 1623 ms 137052 KB Output is correct
41 Correct 0 ms 212 KB Output is correct
42 Correct 694 ms 61156 KB Output is correct
43 Correct 980 ms 84312 KB Output is correct
44 Correct 1605 ms 137156 KB Output is correct
45 Correct 1592 ms 137280 KB Output is correct
46 Correct 1707 ms 80680 KB Output is correct
47 Correct 93 ms 8708 KB Output is correct
48 Correct 798 ms 47008 KB Output is correct
49 Correct 1301 ms 65052 KB Output is correct
50 Correct 2576 ms 138380 KB Output is correct
51 Correct 2675 ms 138460 KB Output is correct
52 Correct 2604 ms 138296 KB Output is correct
53 Correct 2486 ms 138308 KB Output is correct
54 Correct 2560 ms 138628 KB Output is correct
55 Correct 2260 ms 138176 KB Output is correct
56 Correct 2486 ms 138368 KB Output is correct
57 Correct 3004 ms 138524 KB Output is correct
58 Correct 3139 ms 138480 KB Output is correct
59 Correct 3212 ms 138548 KB Output is correct
60 Correct 3137 ms 138480 KB Output is correct
61 Correct 3392 ms 138676 KB Output is correct
62 Correct 3320 ms 138416 KB Output is correct
63 Correct 3281 ms 138404 KB Output is correct
64 Correct 2656 ms 138400 KB Output is correct
65 Correct 2906 ms 138572 KB Output is correct
66 Correct 1173 ms 64500 KB Output is correct
67 Correct 1483 ms 73756 KB Output is correct
68 Correct 1971 ms 83756 KB Output is correct
69 Correct 1720 ms 78272 KB Output is correct
70 Correct 2358 ms 141228 KB Output is correct
71 Correct 2528 ms 141492 KB Output is correct
72 Correct 2659 ms 141512 KB Output is correct
73 Correct 2761 ms 141500 KB Output is correct
74 Correct 2664 ms 135040 KB Output is correct
75 Correct 2549 ms 140616 KB Output is correct
76 Correct 2587 ms 140840 KB Output is correct
77 Correct 2469 ms 135228 KB Output is correct
78 Correct 2686 ms 135104 KB Output is correct
79 Correct 2820 ms 141352 KB Output is correct
80 Correct 3064 ms 135116 KB Output is correct
81 Correct 2721 ms 141196 KB Output is correct
82 Correct 3196 ms 135132 KB Output is correct
83 Correct 3252 ms 141736 KB Output is correct
84 Correct 3254 ms 135156 KB Output is correct
85 Correct 3332 ms 141696 KB Output is correct
86 Correct 3323 ms 135396 KB Output is correct
87 Correct 3339 ms 141824 KB Output is correct
88 Correct 2887 ms 135244 KB Output is correct
89 Correct 2769 ms 141704 KB Output is correct