Submission #714915

#	Time	Username	Problem	Language	Result	Execution time	Memory
714915		MilosMilutinovic	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	129 ms	7736 KiB

triusis

#include <bits/stdc++.h>

using i64 = long long;

const int inf = 1E9;

const int M = 800000;

int mx[M];

void Modify(int p, int l, int r, int i, int v) {
    mx[p] = std::max(mx[p], v);
    if (l == r) {
        return;
    }
    int mid = (l + r) / 2;
    if (i <= mid) {
        Modify(p * 2, l, mid, i, v);
    } else {
        Modify(p * 2 + 1, mid + 1, r, i, v);
    }
}

int Get(int p, int l, int r, int ql, int qr) {
    if (l > r || l > qr || r < ql) {
        return -inf;
    }
    if (ql <= l && r <= qr) {
        return mx[p];
    }
    int mid = (l + r) / 2;
    return std::max(Get(p * 2, l, mid, ql, qr), Get(p * 2 + 1, mid + 1, r, ql, qr));
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;

    n += 1;
    std::vector<int> a(n);
    for (int i = 1; i < n; i++) {
        std::cin >> a[i];
        a[i] -= i * m;
    }

    std::vector<int> xs = a;
    std::sort(xs.begin(), xs.end());
    xs.erase(std::unique(xs.begin(), xs.end()), xs.end());

    int k = (int) xs.size();
    for (int i = 0; i < n; i++) {
        a[i] = std::lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin();
    }

    std::vector<int> dp(n, -inf);
    dp[0] = 1;

    for (int i = 0; i < M; i++) {
        mx[i] = -inf;
    }
    Modify(1, 0, k, a[0], 1);

    for (int i = 1; i < n; i++) {
        dp[i] = Get(1, 0, k, a[i], k) + 1;
        Modify(1, 0, k, a[i], dp[i]);
    }

    std::cout << n - *std::max_element(dp.begin(), dp.end()) << "\n";

    return 0;
}

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