Submission #948432

#	Time	Username	Problem	Language	Result	Execution time	Memory
948432		brendonw	Rabbit Carrot (LMIO19_triusis)	C++17	0 / 100	1 ms	348 KiB

triusis

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
using pll = pair<ll, ll>;
const ll MAX_A = 5e3;

template<typename T>
struct segtree {
	T size;
	vector<T> val;
	T id = 0;

	segtree(T n) {
		size = 1;
		while (size < n) {
			size *= 2;
		}
		val.assign(size * 2, id);
	}

	void update(T i, T v, T x, T lx, T rx) {
		if (rx - lx == 1) {
			val[x] = v;
			return;
		}
		T mid = (lx + rx) / 2;
		if (i < mid) {
			update(i, v, 2 * x + 1, lx, mid);
		} else {
			update(i, v, 2 * x + 2, mid, rx);
		}
		val[x] = max(val[2 * x + 1], val[2 * x + 2]);
	}

	void update(T i, T v) {
		update(i, v, 0, 0, size);
	}

	T query(T l, T r, T x, T lx, T rx) {
		if (r <= lx || l >= rx) {
			return id;
		}
		if (lx >= l && rx <= r) {
			return val[x];
		}
		T mid = (lx + rx) / 2;
		T calc1 = query(l, r, 2 * x + 1, lx, mid);
		T calc2 = query(l, r, 2 * x + 2, mid, rx);
		return max(calc1, calc2);
	}

	T query(T l, T r) {
		if (l > r) {
			return -1;
		}
		if (l == r) {
			return id;
		}
		return query(l, r, 0, 0, size);
	}
};


int solve() {
	ll n, m;
	cin >> n >> m;
	vector<ll> a(n);
	set<ll> heights;
	for (ll i = 0; i < n; ++i) {
		cin >> a[i];
		a[i] -= (i + 1) * m;
		heights.insert(a[i]);
	}
	heights.insert(0);
	ll cnt = 0;
	map<ll, ll> idx;
	for (ll i: heights) {
		if (!idx.count(i)) { idx[i] = ++cnt; }
	}
	segtree<ll> dp(idx.size() + 1);
	for (ll i = 0; i < n; ++i) {
		a[i] = idx[a[i]];
		ll max_prev = dp.query(a[i], idx[0]);
		dp.update(a[i], max_prev + 1);
	}

	cout << n - dp.query(0, idx.size() + 1);

	return 0;
}

#ifndef MY_UNIT_TEST

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

#endif

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