제출 #935082

#제출 시각아이디문제언어결과실행 시간메모리
935082MinaRagy06The short shank; Redemption (BOI21_prison)C++17
0 / 100
18 ms51552 KiB
#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];
void dfs(int i) {
	dp[i] = {0, i};
	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;
	for (int i = 0; i < n; i++) {
		if (a[i] > t && par[i] == i) {
			dfs(i);
			pq.push({dp[i][0], i});
		}
	}
	while (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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...