Submission #1135738

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135738		tvladm	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	124 ms	12180 KiB

triusis

#include <bits/stdc++.h>

#define F first
#define S second

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

const int N = 2e5 + 7;

int f[N];

void add(int i, int x) {
    for (; i < N; i += i & -i) ckmax(f[i], x);
}

int get(int i) {
    int ans = -1e9;
    for (; i >= 1; i -= i & -i) ckmax(ans, f[i]);
    return ans;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    ll n, m; cin >> n >> m;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    
    for (int i = 1; i <= n; ++i) a[i] -= i * m;
    
    {
        vector<int> vals;
        for (int i = 0; i <= n; ++i) vals.push_back(a[i]);
        sort(vals.begin(), vals.end());
        vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
        reverse(vals.begin(), vals.end());
        map<int, int> id;
        for (int i = 0; i < vals.size(); ++i) id[vals[i]] = i + 1;
        for (int i = 0; i <= n; ++i) a[i] = id[a[i]];
    }
    
    vector<int> dp(n + 1, -1e9);
    for (int i = 1; i <= n+1; ++i) f[i] = -1e9; 
    add(a[0], 0);
    for (int i = 1; i <= n; ++i) {
        ckmax(dp[i], get(a[i]) + 1);
        add(a[i], dp[i]);
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) ckmax(ans, dp[i]);
    cout << n - ans << "\n";
}

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