Submission #1306392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306392		Sofiatpc	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	116 ms	4848 KiB

triusis

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define sc second
const int MAXN = 2*1e5+5;
int dp[MAXN], mn[MAXN*4];
pair<int,int> a[MAXN];

void build(int node, int l, int r){
    mn[node] = MAXN;
    if(l == r)return;

    int mid = (l+r)/2, e = node*2,d = node*2+1;
    build(e,l,mid); build(d,mid+1,r);
}

void update(int node, int l ,int r, int i, int x){
    if(i < l || r < i)return;
    if(l == r){
        mn[node] = x;
        return;
    }

    int mid = (l+r)/2, e = node*2,d = node*2+1;
    update(e,l,mid,i,x); update(d,mid+1,r,i,x);
    mn[node] = min(mn[e],mn[d]);
}

int query(int node, int l, int r, int i, int j){
    if(j < l || r < i)return MAXN;
    if(i <= l && r <= j)return mn[node];

    int mid = (l+r)/2, e = node*2,d = node*2+1;
    return min(query(e,l,mid,i,j),query(d,mid+1,r,i,j));
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,m; cin>>n>>m;
    for(int i = 1; i <= n; i++){
        int x; cin>>x;
        a[i].fi = x - m*i; a[i].sc = -i;
    }
    a[n+1].fi = -m*(n+1); a[n+1].sc = -(n+1);
    sort(a,a+n+2);

    build(1,0,n+1);

    for(int id = 0; id <= n+1; id++){
        int i = -a[id].sc;

        if(i != n+1)dp[i] = query(1,0,n+1, i+1,n+1) -i-1;
        update(1,0,n+1, i, dp[i]+i);
    }
    cout<<dp[0]<<"\n";   
}

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