Submission #1202123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202123		IBory	The short shank; Redemption (BOI21_prison)	C++20	80 / 100	431 ms	278256 KiB

prison

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 2000007;
int X[MAX], A[MAX], L[MAX];
pii P[MAX];
vector<int> G[MAX], C;

int DFS(int cur) {
	int ret = A[cur];
	vector<int> T = {0};
	for (int next : G[cur]) {
		T.push_back(DFS(next));
		if (T[0] < T.back()) swap(T[0], T.back());
	}
	for (int i = 1; i < T.size(); ++i) C.push_back(T[i]);
	return ret + T[0];
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, M, T, CN = 0;
	cin >> N >> M >> T;
	for (int i = 1; i <= N; ++i) {
		cin >> X[i];
		if (X[i] <= T) {
			L[i] = ++CN;
			int r = min(N, i + T - X[i]);
			P[CN] = {i, r};
		}
	}

	int TN = 0;
	P[0] = {0, MAX - 1};
	vector<pii> ST1 = {{0, 0}};
	vector<int> ST2 = {0};
	for (int i = 1; i <= N; ++i) {
		if (T < X[i]) A[ST2.back()]++;
		else {
			ST1.emplace_back(L[i], L[i]);
			ST2.push_back(++TN);
		}

		while (1 < ST1.size() && (i == N || P[ST1.back().second].second <= i)) {
			auto [l2, r2] = ST1.back(); ST1.pop_back();
			auto [l1, r1] = ST1.back(); ST1.pop_back();
			int n2 = ST2.back(); ST2.pop_back();
			int n1 = ST2.back(); ST2.pop_back();

			if (n1) {
				ST1.emplace_back(l1, (P[r1].second < P[r2].second ? r2 : r1));
				ST2.push_back(++TN);
				G[TN].push_back(n1);
				G[TN].push_back(n2);
			}
			else {
				ST1.emplace_back(0, 0);
				ST2.push_back(0);
				G[0].push_back(n2);
			}
		}
	}
	A[0] = 0;

	int ans = 0, last = 2e9;
	for (int i = 1; i <= N; ++i) {
		last = min(X[i], last + 1);
		if (last <= T) ans++;
	}

	C.push_back(DFS(0));
	sort(C.begin(), C.end(), greater<int>());
	for (int i = 0; i < min(M, (int)C.size()); ++i) ans -= C[i];

	cout << ans;
	return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 25 / 25
• Subtask 6: 0 / 20