Submission #796993

#	Time	Username	Problem	Language	Result	Execution time	Memory
796993		12345678	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	67 ms	5760 KiB

triusis

#include <bits/stdc++.h>

using namespace std;

const int nx=3e5+5;
int n, m, h[nx], v[nx], c, dp[nx], ans;

struct fenwick
{
    int d[nx];
    void add(int idx, int val)
    {
        while (idx<nx) d[idx]=min(d[idx], val), idx+=(idx&-idx);
    }
    int find(int idx)
    {
        int tmp=INT_MAX;
        while (idx>0) tmp=min(tmp, d[idx]), idx-=(idx&-idx);
        return tmp;
    }
} f;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    ans=n;
    for (int i=1; i<=n; i++) cin>>h[i], h[i]-=i*m, h[i]=-h[i], v[i]=h[i];
    for (int i=0; i<nx; i++) f.d[i]=1e9;
    sort(v, v+n+1);
    int id=lower_bound(v, v+n+1, 0)-v+1;
    f.add(id, -1);
    for (int i=1; i<=n; i++)
    {
        auto idx=lower_bound(v, v+n+1, h[i])-v+1;
        dp[i]=f.find(idx)+i;
        //cout<<i<<' '<<idx<<' '<<f.find(idx)<<' '<<dp[i]<<' '<<h[i]<<'\n';
        f.add(idx, dp[i]-i-1);
        ans=min(ans, dp[i]+n-i);
    }
    cout<<ans;
}

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