Submission #171682

#	Time	Username	Problem	Language	Result	Execution time	Memory
171682		achibasadzishvili	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	423 ms	94492 KiB

triusis

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
using namespace std;
ll n,k,a[200005],ans,dp[2000005];
struct node {
	ll mn;
	node *l,*r;
	node() : mn(n), l(NULL), r(NULL) {}
};

node *root = NULL;

void upd(node *&t, ll l, ll r, ll x, ll y) {
	if(t == NULL)t = new node();
	if(l == r){
		t -> mn = min(t -> mn , y);
		return;
	}
	
	ll m = (l + r) / 2;
	if(x <= m)upd(t->l, l, m, x, y);
    else upd(t->r, m + 1, r, x, y);
	
	t->mn = min((t -> l ? t -> l -> mn : n) , (t -> r ? t -> r -> mn : n));
}
ll cnt(node *t,ll l,ll r,ll x,ll y) {
	if(t){
		if(l >= x && r <= y)
			return t -> mn;
		if(l > y || r < x)return n;
		ll m = (l + r) / 2;
        ll k1,k2;
        k1 = cnt(t->l,l,m,x,y);
        k2 = cnt(t->r,m + 1,r,x,y);
        if(k2 < k1)k1 = k2;
		return k1;
	}
	return n;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> k;
    
    for(int i=1; i<=n; i++)
        cin >> a[i];
    upd(root , 1 , 3000000000 , 1000000000 , 0);
    dp[0] = 0;
    for(int i=1; i<=n; i++){
        ll g = a[i] - i * k + 1000000000;
        ll get = cnt(root , 1 , 3000000000 , g , 3000000000);
        dp[i] = get + i - 1;
        upd(root , 1 , 3000000000 , g , dp[i] - i);
    }
    ans = n;
    for(int i=n; i>=0; i--)
        ans = min(ans , dp[i] + n - i);
    
    cout << ans << '\n';
    
        
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37