#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int oo=1e9+1;
int n,k;
int a[N],dp[N][2];
namespace sub4
{
    int mx_bit,x,temp;
    int bit[N];
    vector <int> ve;
    void rev_bitupdate(int u,int v)
    {
        for (int idx=u;idx>0;idx-=idx&-idx)
        bit[idx]=min(bit[idx],v);
    }
    int rev_bitget(int u)
    {
        int ans=oo;
        for (int idx=u;idx<=mx_bit;idx+=idx&-idx)
        ans=min(ans,bit[idx]);
        return ans;
    }
    void solve()
    {
        ve.clear();
        a[0]=0;
        ve.push_back(0);
        for (int i=1;i<=n;i++)
        ve.push_back(a[i]-i*k);
        sort(ve.begin(),ve.end());
        ve.resize(unique(ve.begin(),ve.end())-ve.begin());
        mx_bit=ve.size();
        for (int i=1;i<=mx_bit;i++)
        bit[i]=oo;
        dp[0][0]=0;
        dp[0][1]=oo;
        x=lower_bound(ve.begin(),ve.end(),a[0])-ve.begin()+1;
        rev_bitupdate(x,0);
        for (int i=1;i<=n;i++)
        {
            dp[i][1]=min(dp[i-1][0],dp[i-1][1])+1;
            x=lower_bound(ve.begin(),ve.end(),a[i]-i*k)-ve.begin()+1;
            temp=rev_bitget(x)+i-1;
            dp[i][0]=temp;
            rev_bitupdate(x,temp-i);
        }
        cout << min(dp[n][0],dp[n][1]);
    }
}
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> k;
    a[0]=0;
    for (int i=1;i<=n;i++)
    cin >> a[i];
    sub4::solve();
}
| # | Verdict | Execution time | Memory | Grader output | 
|---|
| Fetching results... | 
| # | Verdict | Execution time | Memory | Grader output | 
|---|
| Fetching results... | 
| # | Verdict | Execution time | Memory | Grader output | 
|---|
| Fetching results... | 
| # | Verdict | Execution time | Memory | Grader output | 
|---|
| Fetching results... |