Submission #572282

#	Time	Username	Problem	Language	Result	Execution time	Memory
572282		tarunares7250	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	360 ms	24180 KiB

triusis

//ulimit -s unlimited
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vl vector<long long>
#define vi vector<int>
#define vb vector<bool>
#define pql priority_queue<long long>
#define pqp priority_queue<pair<ll,ll> >
#define pqs priority_queue<ll,vl,greater<ll> >
#define md ((ll) 1e9+7)

vl st;
//nl node left;nr node right;ql query left;qr query right;n node key;
ll minq(ll nl,ll nr,ll ql,ll qr,ll n){
    if(qr>=nr && ql<=nl){
        return st[n];
    }
    else if(qr<nl || ql>nr){
        return md;
    }
    return min(minq(nl,(nl+nr)/2,ql,qr,2*n),minq((nl+nr)/2 + 1,nr,ql,qr,2*n+1));
}

void updateq(ll nl,ll nr,ll n,ll i,ll v){
    if(nl == nr && nl == i){
        st[n] = min(v,st[n]);
        return;
    }
    ll mid = (nl+nr)/2;
    if(i<=mid){
        updateq(nl,mid,2*n,i,v);
    }
    else{
        updateq(mid+1,nr,2*n+1,i,v);
    }
    st[n] = min(st[2*n],st[2*n+1]);
}


void solve(){

    ll i,j,k,n,m;
    cin>>n>>m;

    ll a[n+1];
    a[0] = 0;
    for(i=1;i<=n;i++){
        cin>>a[i];
        a[i] -= i*m;
    }

    map<ll,ll> cc;
    for(i=0;i<=n;i++){
        cc[a[i]] = 0;
    }
    i = 0;
    for(auto &c:cc){
        c.second = i;
        i++;
    }

    k = cc.size();
    k++;
    st.resize(4*k,md);
    ll dp[n+1];

    for(i=n;i>=0;i--){
        ll ans = minq(0,k-1,0,cc[a[i]],1);
        dp[i] = ans-i-1;
        dp[i] = min(dp[i],n-i);
        updateq(0,k-1,1,cc[a[i]],dp[i]+i);
    }
    cout<<dp[0]<<"\n";

    // for(i=0;i<=n;i++){
    //     cout<<dp[i]<<" ";
    // }
    // cout<<"\n";

    // for(auto c:cc){
    //     cout<<c.first<<","<<c.second<<" ";
    // }
    // cout<<"\n";
    // cout<<cc.size()<<"\n";


}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;
    //cin >> t;
    t = 1;
    while(t--)
        solve();
    return 0;
}

Compilation message (stderr)

triusis.cpp: In function 'void solve()':
triusis.cpp:43:10: warning: unused variable 'j' [-Wunused-variable]
   43 |     ll i,j,k,n,m;
      |          ^

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