Submission #417804

#	Time	Username	Problem	Language	Result	Execution time	Memory
417804		Blagojce	The short shank; Redemption (BOI21_prison)	C++11	70 / 100	832 ms	9668 KiB

prison

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
  
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
const ll inf = 2e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;


mt19937 _rand(time(NULL));
const int mxn = 2e5;

ll n, d, T;
ll a[mxn];
ll pr[mxn];


pii seg[2*mxn];
ll t[2*mxn];

int l(int k){
	return 2*k;
}
int r(int k){
	return 2*k+1;
}

void push(int k){
	t[l(k)] += t[k];
	t[r(k)] += t[k];
	t[k] = 0;
}
void upd(int k){
	pii lef = {seg[l(k)].st + t[l(k)], seg[l(k)].nd};
	pii rig = {seg[r(k)].st + t[r(k)], seg[r(k)].nd};
	
	seg[k] = min(lef, rig);
}

void build(int k, int l, int r){
	seg[k] = {inf, 0};
	t[k] = 0;
	if(l == r){
		return;
	}
	int mid = (l+r)/2;
	build(::l(k), l, mid);
	build(::r(k), mid+1, r);

}

void Insert(int k, int l, int r, int pos, ll val, ll C){
	if(r < pos || pos < l) return;
	if(l == r){
		seg[k].st = val;
		seg[k].nd = C;
		t[k] = 0;
		return;
	}
	push(k);
	int mid = (l+r)/2;
	Insert(::l(k), l, mid, pos, val, C);
	Insert(::r(k), mid+1, r, pos, val, C);
	upd(k);
}


void update(int k, int l, int r, int x, int y, ll val){
	if(r < x || y < l) return;
	if(x <= l && r <= y){
		t[k] += val;
		return;
	}
	push(k);
	int mid = (l+r)/2;
	update(::l(k), l, mid, x, y, val);
	update(::r(k), mid+1, r, x, y, val);
	upd(k);
}

pii dp[mxn];

int TOT = 0;
int sure = 0;
void g(ll lambda){
	build(1, 0, n);
	
	Insert(1, 0, n, 0, 0, 0);
	
	fr(i, 0, n){
		if(pr[i] != -1 && pr[i] != i){
			update(1, 0, n, 0, pr[i], 1); 
		}
		
		pii bst = {seg[1].st + t[1], seg[1].nd};
		
		dp[i] = {bst.st + lambda, bst.nd+1};
	
		Insert(1, 0, n, i+1, dp[i].st, dp[i].nd);
	}
	dp[n-1].nd--;
	dp[n-1].st -= lambda;
}


ll aliens(){
	
	
	ll l = 0, r = n+1;
	ll best_lambda = 0;
	
	while(l <= r){
		ll mid = (l+r)/2;
		g(mid);
		if(dp[n-1].nd >= d){
			best_lambda = mid;
			l = mid+1;
		}
		else{
			r = mid-1;
		}
	}
	
	
	g(best_lambda);
	
	if(dp[n-1].nd > d){
		ll a1 = dp[n-1].st - best_lambda*dp[n-1].nd;
		ll c1 = dp[n-1].nd;
		g(best_lambda+1);
		ll a2 = dp[n-1].st - (best_lambda+1)*dp[n-1].nd;
		ll c2 = dp[n-1].nd;
		return a2 + (a1-a2)*(d-c2)/(c1-c2);
		
	}
	
	
	return dp[n-1].st - best_lambda*dp[n-1].nd;
}


void solve(){
	cin >> n >> d >> T;
	fr(i, 0, n){
		cin >> a[i];
	}
	stack<int> S;
	fr(i, 0, n){
		if(a[i] <= T){
			pr[i] = i;
			while(!S.empty() && a[S.top()] + i - S.top() >= a[i]){
				S.pop();
				}
			S.push(i);
		}
		else{
			while(!S.empty() && a[S.top()] + i - S.top() > T){
				S.pop();
			}
			if(S.empty()){
				pr[i] = -1;
			}
			else{
				pr[i] = S.top();
			}
		}
	}
	fr(i, 0, n){
		if(pr[i] == -1) continue;
		if(pr[i] == i) sure ++;	
		TOT ++;
	}
	cout<<sure+aliens()<<endl;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solve();
}
/*
6 1 10
8 11 11 1 11 11
 

*/

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