Submission #935095

#	Time	Username	Problem	Language	Result	Execution time	Memory
935095		MinaRagy06	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	370 ms	264624 KiB

prison

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

const int N = 2'000'005;
int par[N];
array<int, 2> dp[N];
vector<int> adj[N];
bool vis[N], in[N];
void dfs(int i) {
	dp[i] = {0, i};
	in[i] = 1;
	for (auto nxt : adj[i]) {
		dfs(nxt);
		array<int, 2> val = dp[nxt];
		val[0]++;
		dp[i] = max(dp[i], val);
	}
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n, d, t;
	cin >> n >> d >> t;
	int a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	stack<int> s;
	int ans = n;
	for (int i = n - 1; i >= 0; i--) {
		while (s.size() && s.top() <= t + i - a[i]) {
			s.pop();
		}
		par[i] = i;
		if (a[i] > t) {
			if (s.size()) par[i] = s.top();
			s.push(i);
		}
	}
	for (int i = 0; i < n; i++) {
		if (par[i] == i) continue;
		adj[par[i]].push_back(i);
	}
	priority_queue<array<int, 2>> pq;
	while (s.size()) {
		vis[s.top()] = 1;
		s.pop();
	}
	for (int i = n - 1; i >= 0; i--) {
		if (a[i] > t && !in[i] && !vis[i]) {
			dfs(i);
			pq.push({dp[i][0], i});
		}
	}
	while (d-- && pq.size()) {
		array<int, 2> v = pq.top();
		pq.pop();
		int i = dp[v[1]][1];
		while (1) {
			for (auto nxt : adj[i]) {
				if (!vis[nxt]) {
					pq.push({dp[nxt][0], nxt});
				}
			}
			vis[i] = 1;
			if (i == v[1]) break;
			i = par[i];
		}
	}
	for (int i = 0; i < n; i++) {
		ans -= vis[i];
	}
	cout << ans << '\n';
	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