Submission #839206

#	Time	Username	Problem	Language	Result	Execution time	Memory
839206		MetalPower	The short shank; Redemption (BOI21_prison)	C++14	100 / 100	351 ms	283328 KiB

prison

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

#define pii pair<int, int>
#define fi first
#define se second

const int MX = 2e6 + 10;

int N, D, T, arr[MX], st[MX], nxt[MX], f[MX];
vector<int> adj[MX], root;

int dep[MX], par[MX], max_dep[MX], pos_dep[MX];
bool rem[MX];

void dfs(int u){
	if(dep[u] > max_dep[u]){
		max_dep[u] = dep[u];
		pos_dep[u] = u;
	}
	for(int nxt : adj[u]){
		par[nxt] = u;
		dep[nxt] = dep[u] + 1;
		dfs(nxt);
		if(max_dep[nxt] > max_dep[u]){
			max_dep[u] = max_dep[nxt];
			pos_dep[u] = pos_dep[nxt];
		}
	}
}

priority_queue<pii> pq;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N >> D >> T;
	for(int i = 0; i < N; i++) cin >> arr[i];

	memset(f, -1, sizeof f);
	memset(nxt, -1, sizeof nxt);

	vector<pii> stk;
	vector<int> pos;

	int sum = 0;

	for(int i = 0; i < N; i++){
		if(arr[i] <= T){
			st[i] = 0; sum++;
			stk.push_back({i, arr[i]});
		}else if(arr[i] > T){
			for(; !stk.empty(); ){
				if(i - stk.back().fi <= T - stk.back().se){
					f[i] = stk.back().fi;
					break;
				}
				stk.pop_back();
			}
			if(f[i] == -1) st[i] = 0;
			else{
				sum++;
				for(; !pos.empty() && pos.back() > f[i]; ){
					nxt[pos.back()] = i, pos.pop_back();
				}
				pos.push_back(i);
				st[i] = 1;
			}
		}
	}

	for(int i = 0; i < N; i++){
		if(st[i] && nxt[i] != -1){
			adj[nxt[i]].push_back(i);
		}else if(st[i] && nxt[i] == -1){
			root.push_back(i);
		}
	}

	for(int nd : root){
		par[nd] = -1;
		dep[nd] = 1;
		dfs(nd);
		pq.push({max_dep[nd], nd});
	}

	int tot = 0;
	for(int j = 0; j < D; j++){
		if(pq.empty()) break;

		int nd = pq.top().se, lw = pos_dep[nd];
		tot += pq.top().fi; pq.pop();

		for(; lw != -1 && !rem[lw]; lw = par[lw]){
			rem[lw] = true;
			for(int nxt : adj[lw]){
				if(rem[nxt]) continue;
				pq.push({max_dep[nxt] - dep[nxt] + 1, nxt});
			}
		}
	}

	cout << sum - tot << '\n';
}

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