Submission #589905

#	Time	Username	Problem	Language	Result	Execution time	Memory
589905		WongChun1234	The short shank; Redemption (BOI21_prison)	C++14	100 / 100	430 ms	229072 KiB

prison

#include<bits/stdc++.h>
using namespace std;
const int N=2000050;
int n,d,t,a[N],par[N],diff[N],ans,pt,mx[N],mv[N];
bool del[N];
vector<int> stk,nde[N],ch[N];
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>d>>t;
	ans=pt=n;
	for (int i=1;i<=n;i++){
		cin>>a[i];
		diff[i]+=diff[i-1];
		if (a[i]<=t) diff[i]++,diff[min(i+t-a[i]+1,N-2)]--;
		else if (diff[i]) par[i]=i;
		else ans--;
	}
	for (int i=1;i<=n;i++){
		while (stk.size()){
			if (a[stk.back()]<=t){
				if (stk.back()+t-a[stk.back()]<i) stk.pop_back();
				else break;
			}else if (a[i]>t&&diff[i]){
				par[stk.back()]=i;
				ch[i].push_back(stk.back());
				stk.pop_back();
			}else break;
		}
		stk.push_back(i);
	}
	//for (int i=1;i<=n;i++) cout<<par[i]<<"\n";
	for (int i=1;i<=n;i++){
		if (a[i]<=t||!diff[i]) continue;
		mx[i]=1;
		for (int j:ch[i]){
			if (j==i) continue;
			if (mx[j]+1>mx[mv[i]]) mx[i]=mx[j]+1,mv[i]=j;
		}
		nde[mx[i]].push_back(i);
	}
	//for (int i=1;i<=n;i++) cout<<mx[i]<<" "<<mv[i]<<"\n";
	while (pt){
		for (int j:nde[pt]){
			if (del[j]) continue;
			//cout<<j<<" "<<pt<<"!\n";
			if (!d) goto done;
			ans-=pt;
			d--;
			for (int k=j;k;k=mv[k]){
				del[k]=1;
			}
		}
		pt--;
	}
	done:;
	cout<<ans<<"\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