Submission #491301

#	Time	Username	Problem	Language	Result	Execution time	Memory
491301		vicyan1611	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	96 ms	7732 KiB

triusis

#include <bits/stdc++.h>

using namespace std;
const long long Nmax = 2e5 + 5;

long long n, a[Nmax], m, b[Nmax], bit[Nmax];

void update(long long x, long long val)
{
    for (; x < Nmax; x += x & -x)
    {
        bit[x] = max(bit[x], val);
    }
}

long long gett(long long x)
{
    long long res = 0;
    for (; x > 0; x -= x  & -x)
    {
        res = max(res, bit[x]);
    }
    return res;
}

int main()
{
    cin >> n >> m;
    for (long long i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    long long nb = 0;
    vector <long long> q;
    for (long long i = 1; i <= n; ++i)
    {
        if (a[i] > m * i) continue;
        b[++nb] = i * m - a[i];
        q.push_back(b[nb]);
    }
    sort(q.begin(), q.end());
    for (long long i = 1; i <= nb; ++i)
    {
        b[i] = lower_bound(q.begin(), q.end(), b[i]) - q.begin() + 1;
    }
    long long res = 0;
    for (long long i = 1; i <= nb; ++i)
    {
        long long t = gett(b[i]) + 1;
        update(b[i], t);
        res = max(res, t);
    }
    cout << n - res;
    return 0;
}

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