Submission #1284656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284656		dobri_oke	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	44 ms	6108 KiB

triusis

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define int long long

const int N = 2e5+100;
int n, m, t[N * 4], a[N];
void build(int v, int l, int r){
    t[v] = 1e18;
    if(l == r) return;
    int m = (l + r) / 2;
    build(v + v, l, m);
    build(v + v + 1, m + 1, r);
}
void upd(int v, int l, int r, int i, int x){
    if(l == r){
        t[v] = min(t[v], x);
        return;
    }
    int m = (l + r) / 2;
    if(i <= m) upd(v + v, l, m, i, x);
    else upd(v + v + 1, m + 1, r, i, x);
    t[v] = min(t[v + v], t[v + v + 1]);
}
int get(int v, int l, int r, int x){
    if(l == r) return l;
    int m = (l + r) / 2;
    if(t[v + v + 1] <= x) return get(v + v + 1, m + 1, r, x);
    return get(v + v, l, m, x);
}
void solve(){
    cin >> n >> m;
    a[0] = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        a[i] = i * m - a[i];
    }
    build(1, 0, n);
    upd(1, 0, n, 0, -1e18);
    for(int i = 1; i <= n; i++){
        if(a[i] < 0) continue;
        int f = get(1, 0, n, a[i]);
        upd(1, 0, n, f + 1, a[i]);
    }
    cout << n - get(1, 0, n, 1e17);
}

signed main(){   
    ios_base::sync_with_stdio(0);   cin.tie(0);
    //freopen("promote.in","r",stdin);
    //freopen("promote.out","w",stdout);
    int tt=1;
   // cin >> tt;
    while(tt--){
        solve();
    }
}

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