Submission #1189348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189348		justinlgl20	The short shank; Redemption (BOI21_prison)	C++20	0 / 100	223 ms	164764 KiB

prison

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
#define all(x) (x).begin(), (x).end()
 
template<template<typename> class Container, typename G>
ostream& operator<<(ostream& os, Container<G> x) {
    int f = 0; os << '{'; for (auto &i: x) os << (f++ ? ", " : ""), os << i; os << "}";
    return os;
}
 
void _print() {cerr << "]\n";}
 
template<typename T, typename... V>
void _print(T t, V... v) {cerr << t; if (sizeof...(v)) cerr <<", "; _print(v...);}
 
#ifdef DEBUG
#define dbg(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif

#define pii pair<int, int>
#define f first
#define s second

vector<int> adj[2000005];
multiset<int> vals[2000005];

void solve(int u,int p){
	bool kids=false;
	pii big={-10ll,-1ll};
	for(int i:adj[u]){
		if(i==p)continue;
		kids=true;
		solve(i,u);
		big=max(big,make_pair((int)vals[i].size(),i));
	}
	if(!kids){
		vals[u].insert(1);
	}else{
		swap(vals[u],vals[big.s]);
		for(int i:adj[u]){
			if(i==p or i==big.s)continue;
			for(int j:vals[i]){
				vals[u].insert(j);
			}
		}
		int v=(*vals[u].rbegin());
		vals[u].erase(vals[u].find(v));
		vals[u].insert(v+1ll);
	}
}

int32_t main() {
	int n,d,t;cin>>n>>d>>t;vector<int>a(n),par(n,-1);for(int i=0;i<n;i++){cin>>a[i];a[i]=max(0ll, t-a[i]+1ll);}
	stack<int> s;
	for(int i=n-1;i>=0;i--){
		if(a[i]){
			// range is from [i,x] 
			int x=i+a[i]-1ll;
			while(s.size() and s.top()<=x){
				s.pop();
			}
		}else {
			if(s.size()){
				adj[s.top()].push_back(i);
				par[i]=s.top();
				dbg(i,s.top());
			}
			s.push(i);
		}
	}
	multiset<int> sw;
	for(int i=0;i<n;i++){
		if(par[i]==-1 and a[i]==0){
			solve(i,-1);
			for(int j:vals[i]){
				sw.insert(j);
			}
		}
	}
	int ans=0;
	dbg(sw);
	auto x=sw.rbegin();
	for(int i=0;i<d and x!=sw.rend();i++,x++){
		ans+=(*x);
	}
	cout<<n-ans<<"\n";

}

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