Submission #213064

#	Time	Username	Problem	Language	Result	Execution time	Memory
213064		qkxwsm	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	40 ms	4984 KiB

triusis

#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

const int MAXN = 200013;

int N, M;
ll arr[MAXN];
vl compress;

int32_t main()
{
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(4);
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N >> M; N++;
    arr[0] = 0;
    FOR(i, 1, N)
    {
        cin >> arr[i];
        arr[i] = i * M - arr[i];
        // compress.PB(arr[i]);
    }
    // FOR(i, 1, N)
    // {
    //     cerr << arr[i] << ' ';
    // }
    // cerr << endl;
    // sort(ALL(compress));
    // compress.erase(unique(ALL(compress)), compress.end());
    // FOR(i, 0, N)
    // {
    //     arr[i] = LB(ALL(compress), arr[i]) - compress.begin();
    // }
    vi dp;
    dp.PB(0);
    FOR(i, 1, N)
    {
        if (arr[i] < 0) continue;
        // int x = arr[i];
        int idx = UB(ALL(dp), arr[i]) - dp.begin();
        if (idx >= SZ(dp)) dp.PB(69);
        dp[idx] = arr[i];
    }
    cout << N - SZ(dp) << '\n';
    return 0;
}

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