Submission #916975

#	Time	Username	Problem	Language	Result	Execution time	Memory
916975		NK_	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	882 ms	209864 KiB

prison

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())
#define mp make_pair

template<class T> using V = vector<T>;
template<class T> using pq = priority_queue<T, vector<T>, less<T>>;

using vi = V<int>;
using pi = pair<int, int>;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, D, T; cin >> N >> D >> T;
	vi A(N); for(auto& x : A) cin >> x;

	V<vi> E(N);
	for(int i = 0; i < N; i++) {
		A[i] = max(T + 1 - A[i], 0);
		// cout << i << " => " << A[i] << endl;
		int r = i + A[i];
		if (r < N) E[r].pb(i);
	}
	// cout << endl;

	set<int> R; int ans = 0;

	vi LX, RX; 
	for(int i = 0; i < N; i++) {
		R.insert(i);
		for(auto& x : E[i]) R.erase(x);

		// cout << i << " ==> ";
		// for(auto& x : R) cout << x << " ";
		// cout << endl;

		if (A[i] == 0) {
			if (sz(R)) {
				LX.pb(*rbegin(R));
				RX.pb(max(LX.back(), (sz(RX) ? RX.back() : -1)));
				// cout << i << " => " << LX.back() << " " << RX.back() << endl;
			} else {
				// cout << i << " => {}" << endl;
				ans++;
			}

		} 
		// else {
		// 	// cout << i << " " << A[i] << endl;
		// }
	}	


	int M = sz(LX);
	vi ord(M); iota(begin(ord), end(ord), 0);
	sort(begin(ord), end(ord), [&](int x, int y) {
		return mp(LX[x], -RX[x]) < mp(LX[y], -RX[y]);

	});

	vi P, C, I, stk = {-1}; // parent, count
	for(auto& i : ord) {
		// cout << i << " => " << LX[i] << " " << RX[i] << endl;
		int u = sz(C); 
		while(stk.back() != -1 && RX[I[stk.back()]] < LX[i]) stk.pop_back();

		int par = stk.back();
		if (par == -1 || mp(LX[I[par]], RX[I[par]]) != mp(LX[i], RX[i])) {
			C.pb(1); I.pb(i); P.pb(par); stk.pb(u);
		} else C.back()++; 
	}

	int K = sz(P);
	V<vi> chd(K); for(int i = 0; i < K; i++) {
		if (P[i] != -1) {
			chd[P[i]].pb(i);
			// cout << i << " <--> " << P[i] << endl;
		}
	}

	vi mx(K), vis(K), taken(K, 0), S(K, 0); 
	function<void(int)> dfs = [&](int u) {
		S[u] += C[u]; mx[u] = u; vis[u] = 1; 
		for(auto& v : chd[u]) {
			S[v] += S[u];
			dfs(v); 
			if (S[mx[u]] < S[mx[v]]) mx[u] = mx[v];
		}	
	};

	pq<pi> q; for(int i = 0; i < K; i++) if (P[i] == -1) {
		dfs(i); q.push(mp(S[mx[i]], mx[i]));
		// cout << i << " --> " << mx[i] << endl;
	}

	while(D && sz(q)) {
		auto [amt, u] = q.top(); q.pop();
		D--; ans += max(amt, 0); 
		// cout << "T: " << amt << " " << u << endl;

		while(u != -1) {
			taken[u] = 1;
			for(auto& v : chd[u]) if (!taken[v]) {
				P[v] = -1;
				// cout << "ROOT: " << v << " => " << mx[v] << " " << S[mx[v]] - rem[v] << endl;
				q.push(mp(S[mx[v]] - S[u], mx[v]));
			}
			u = P[u];
		}
	}

	// cout << ans << endl;

	cout << N - ans << nl;

	exit(0-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