Submission #426337

#	Time	Username	Problem	Language	Result	Execution time	Memory
426337		dolphingarlic	The short shank; Redemption (BOI21_prison)	C++14	100 / 100	452 ms	125052 KiB

prison

#include <bits/stdc++.h>
using namespace std;

int depth[2000001], mx_child[2000001];
vector<int> children[2000001];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, d, tx;
	cin >> n >> d >> tx;

	int ans = n, glob_mx = 0, loc_mx = 0;
	priority_queue<pair<int, int>> pq;
	stack<pair<int, int>> stck;
	for (int i = 1; i <= n; i++) {
		int t;
		cin >> t;
		glob_mx = max(glob_mx, i + tx - t);
		loc_mx = max(loc_mx, i + tx - t);
		if (stck.size())
			stck.top().second = max(stck.top().second, loc_mx);
		if (t > tx) {
			if (glob_mx < i) ans--;
			else {
				depth[i] = 1;
				while (stck.size()) {
					int node, tmp_mx;
					tie(node, tmp_mx) = stck.top();
					if (tmp_mx >= i) break;
					children[i].push_back(node);
					if (depth[node] + 1 > depth[i]) {
						depth[i] = depth[node] + 1;
						mx_child[i] = node;
					}
					stck.pop();
					if (stck.size())
						stck.top().second = max(stck.top().second, tmp_mx);
				}
				loc_mx = i + tx - t;
				stck.push({i, loc_mx});
			}
		}
	}
	while (stck.size()) {
		int root = stck.top().first;
		pq.push({depth[root], root});
		stck.pop();
	}

	while (d-- && pq.size()) {
		pair<int, int> curr = pq.top();
		pq.pop();
		ans -= curr.first;
		int node = curr.second;
		while (node) {
			for (int i : children[node]) if (i != mx_child[node])
				pq.push({depth[i], i});
			node = mx_child[node];
		}
	}
	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: 20 / 20