oj.uz

Submission #591004

# Submission time Handle Problem Language Result Execution time Memory
591004 2022-07-06T17:10:59 Z dutinmeow Election (BOI18_election) C++17
100 / 100
 486 ms 44812 KB 
#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;
	string S;
	cin >> N >> S;
	vector<int> A(N);
	for (int i = 0; i < N; i++)
		A[i] = S[i] == 'C' ? 1 : -1;

	using st_node_t = struct { int pre, suf, ans, sum; };
	vector<st_node_t> st_tree(4 * N);

	auto st_pull = [&](const st_node_t &a, const st_node_t &b) -> st_node_t {
		return st_node_t{
			max(a.pre, a.sum + b.pre),
			max(b.suf, b.sum + a.suf),
			max({a.ans, b.ans, a.suf + b.pre}),
			a.sum + b.sum
		};
	};

	y_combinator([&](auto st_build, int t, int tl, int tr) -> void {
		if (tl == tr) {
			st_tree[t] = st_node_t{max(A[tl], 0), max(A[tl], 0), max(A[tl], 0), A[tl]};
			return;
		}
		int tm = (tl + tr) / 2;
		st_build(t * 2, tl, tm);
		st_build(t * 2 + 1, tm + 1, tr);
		st_tree[t] = st_pull(st_tree[t * 2], st_tree[t * 2 + 1]);
	})(1, 0, N - 1);

	auto st_query = y_combinator([&](auto st_query, int l, int r, int t, int tl, int tr) -> st_node_t {
		if (l > r)
			return st_node_t{0, 0, 0, 0};
		if (l <= tl && tr <= r)
			return st_tree[t];
		int tm = (tl + tr) / 2;
		if (r <= tm)
			return st_query(l, r, t * 2, tl, tm);
		if (tm < l)
			return st_query(l, r, t * 2 + 1, tm + 1, tr);
		return st_pull(st_query(l, r, t * 2, tl, tm), st_query(l, r, t * 2 + 1, tm + 1, tr));
	});

	int Q;
	cin >> Q;
	while (Q--) {
		int l, r;
		cin >> l >> r;
		l--, r--;
		auto q = st_query(l, r, 1, 0, N - 1);
		cout << q.ans - q.sum << '\n';
	}
}

Compilation message

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

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 464 KB Output is correct
5 Correct 2 ms 468 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 464 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 45 ms 6308 KB Output is correct
7 Correct 46 ms 6208 KB Output is correct
8 Correct 43 ms 6216 KB Output is correct
9 Correct 43 ms 6264 KB Output is correct
10 Correct 45 ms 6236 KB Output is correct
11 Correct 48 ms 6428 KB Output is correct
12 Correct 53 ms 6400 KB Output is correct
13 Correct 46 ms 6380 KB Output is correct
14 Correct 45 ms 6348 KB Output is correct
15 Correct 50 ms 6336 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 464 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 45 ms 6308 KB Output is correct
7 Correct 46 ms 6208 KB Output is correct
8 Correct 43 ms 6216 KB Output is correct
9 Correct 43 ms 6264 KB Output is correct
10 Correct 45 ms 6236 KB Output is correct
11 Correct 48 ms 6428 KB Output is correct
12 Correct 53 ms 6400 KB Output is correct
13 Correct 46 ms 6380 KB Output is correct
14 Correct 45 ms 6348 KB Output is correct
15 Correct 50 ms 6336 KB Output is correct
16 Correct 438 ms 43816 KB Output is correct
17 Correct 387 ms 43400 KB Output is correct
18 Correct 474 ms 43664 KB Output is correct
19 Correct 358 ms 43128 KB Output is correct
20 Correct 432 ms 42928 KB Output is correct
21 Correct 442 ms 44628 KB Output is correct
22 Correct 428 ms 44576 KB Output is correct
23 Correct 465 ms 44812 KB Output is correct
24 Correct 486 ms 44604 KB Output is correct
25 Correct 435 ms 44032 KB Output is correct