제출 #705298

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
705298		robertanechita1	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	107 ms	7516 KiB

triusis

#include <bits/stdc++.h>

using namespace std;

const int MaxN = 200005;
int n, m, a[MaxN], cnt;
long long b[MaxN], aib[MaxN], ans , dp[MaxN];
pair <int, int> c[MaxN];

void Update(int poz, long long val){
    for(int i = poz; i <= cnt; i += (i & -i))
        aib[i] = max(aib[i], val);
}

long long Query(int poz){
    long long s = 0;
    for(int i = poz; i > 0; i -= (i & -i))
        s = max(s, aib[i]);
    return s;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        if(1LL * m * i - a[i] >= 0){
            b[++cnt] = 1LL * m * i - a[i];
            c[cnt] = {b[cnt], cnt};
        }
    }
    sort(c + 1, c + cnt + 1);
    int val = 1;
    b[c[1].second] = 1;
    for(int i = 2; i <= cnt; i++){
        if(c[i].first != c[i - 1].first)
            val++;
        b[c[i].second] = val;
    }

    for(int i = 1; i <= cnt; i++){
        dp[i] = max(dp[i], 1 + Query(b[i]));
        Update(b[i], dp[i]);
        ans = max(ans, dp[i]);
    }
    cout << n - ans << "\n";
    return 0;
}

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