Submission #565463

#	Time	Username	Problem	Language	Result	Execution time	Memory
565463		CSQ31	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	477 ms	275152 KiB

prison

#pragma GCC optimize("Ofast") 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e6+1;
int a[MAXN],lf[MAXN],par[MAXN],sub[MAXN],nxt[MAXN];
bool ded[MAXN];
vector<int>adj[MAXN];
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
void dfs(int v){
	int mx = 0;
	for(int x:adj[v]){
		dfs(x);
		if(mx < sub[x]){
			mx = sub[x];
			nxt[v] = x;
		}
	}
	sub[v] = mx+1;
	
}
int main()
{
	owo
	int n,d,t;
	cin>>n>>d>>t;
	for(int i=0;i<n;i++){
		cin>>a[i];
		lf[i] = -1;
	}
	int ans = 0;
	stack<int>stk;
	for(int i=0;i<n;i++){
		if(a[i]<=t){
			ans++;
			while(!stk.empty() && a[stk.top()] >= a[i])stk.pop();
			stk.push(i); 
		}else{
			while(!stk.empty() && i-stk.top() > t-a[stk.top()])stk.pop();
			if(stk.empty())continue;
			ans++;
			lf[i] = stk.top();
		}
	}
	while(!stk.empty())stk.pop();
	for(int i=n-1;i>=0;i--){
		if(lf[i] == -1)continue;
		while(!stk.empty() && lf[stk.top()] >= i)stk.pop();
		if(!stk.empty()){
			par[i] = stk.top();
			adj[par[i]].push_back(i);
		}
		else par[i] = -1;
		
		while(!stk.empty() && lf[i] <= lf[stk.top()])stk.pop();
		stk.push(i);
		//cout<<i<<" "<<par[i]<<'\n';
	}
	for(int i=0;i<n;i++)nxt[i] = -1;
	for(int i=0;i<=n-1;i++){
		if(par[i] == -1)dfs(i);
	}
	vector<vector<int>> s(n+1);
	//for(int i=0;i<n;i++)cout<<lf[i]<<" ";
	//cout<<'\n';
	for(int i=0;i<n;i++){
		//cout<<sub[i]<<" ";
		s[sub[i]].push_back(i);
	}
	//cout<<'\n';
	for(int i=n;i>=1;i--){
		for(int x:s[i]){
			if(ded[x])continue;
			ans-=i;
			int v = x;
			while(v!=-1){
				ded[v] = 1;
				v = nxt[v];
			}
			d--;
			if(!d)break;
		}
		if(!d)break;
		
	}
	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