제출 #565389

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
565389		CSQ31	The short shank; Redemption (BOI21_prison)	C++17	10 / 100	568 ms	250732 KiB

prison

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e6+1;
int a[MAXN],lf[MAXN];
bool ded[MAXN];
vector<int>T[4*MAXN];
void add(int v,int l,int r,int tl,int tr,int x){
	if(l>r)return;
	if(l==tl && r==tr)T[v].push_back(x);
	else{
		int tm = (tl+tr)/2;
		add(2*v,l,min(r,tm),tl,tm,x);
		add(2*v+1,max(tm+1,l),r,tm+1,tr,x);
	}
}
vector<int>del;
void get(int v,int l,int r,int pos){
	for(int x:T[v]){
		if(ded[x])continue;
		ded[x] = 1;
		del.push_back(x);
	}
	T[v].clear();
	if(l==r)return;
	int tm = (l+r)/2;
	if(tm<=pos)get(2*v,l,tm,pos);
	else get(2*v+1,tm+1,r,pos);
}
pair<int,int> mx[4*MAXN];
int lazy[4*MAXN];
void upd(int v,int l,int r,int tl,int tr,int x){
	if(l>r)return;
	if(l==tl && r==tr){
		mx[v].first+=x;
		lazy[v]+=x;
		return;
	}
	int tm = (tl+tr)/2;
	upd(2*v,l,min(r,tm),tl,tm,x);
	upd(2*v+1,max(tm+1,l),r,tm+1,tr,x);
	mx[v] = max(mx[2*v],mx[2*v+1]);
	mx[v].first+=lazy[v];
}
void build(int v,int l,int r){
	if(l==r){
		mx[v].second = l;
		mx[v].first = a[l];
		return;
	}
	int tm = (l+r)/2;
	build(2*v,l,tm);
	build(2*v+1,tm+1,r);
	mx[v] = max(mx[2*v],mx[2*v+1]);
	
}
int main()
{
	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();
		}
	}
	vector<int>s(n,0);
	//cout<<ans<<'\n';
	//for(int i=0;i<n;i++)cout<<lf[i]<<" ";
	//cout<<'\n';
	for(int i=0;i<n;i++){
		if(lf[i] != -1){
			s[lf[i]]++;
			s[i]--;
			add(1,lf[i],i-1,0,n-1,i);
		}
	}
	for(int i=1;i<n;i++)s[i]+=s[i-1];
	for(int i=0;i<n;i++)a[i] = s[i];
	build(1,0,n-1);
	for(int k=0;k<d;k++){
		if(mx[1].first<=0)break;
		ans-=mx[1].first;
		//cout<<mx[1].first<<" "<<v<<'\n';
		del.clear();
		get(1,0,n-1,mx[1].second);
		for(int x:del)upd(1,lf[x],x-1,0,n-1,-1);
	}
	cout<<ans<<'\n';
}

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