Submission #565118

#	Time	Username	Problem	Language	Result	Execution time	Memory
565118		acatmeowmeow	Rabbit Carrot (LMIO19_triusis)	C++11	100 / 100	369 ms	24172 KiB

triusis

#include <bits/stdc++.h>

using namespace std;

#define int long long 

void update(vector<int>&tree, int v, int tl, int tr, int k, int x) {
	if (tl == tr) tree[v] = max(tree[v], x);
	else {
		int tm = (tl + tr)/2;
		if (k <= tm) update(tree, v*2, tl, tm, k, x);
		else update(tree, v*2 + 1, tm + 1, tr, k, x);
		tree[v] = max(tree[v*2], tree[v*2 + 1]);
	}
}

int query(vector<int>&tree, int v, int tl, int tr, int l, int r) {
	if (l > r) return -1e18;
	else if(tl == l && tr == r) return tree[v];
	else {
		int tm = (tl + tr)/2;
		return max(query(tree, v*2, tl, tm, l, min(tm, r)), query(tree, v*2 + 1, tm + 1, tr, max(tm + 1, l), r));
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	cin >> n >> m;
	vector<int> diff(n + 5);
	map<int, int> mp = {{0, 1}};
	for (int i = 1; i <= n; i++) {
		int h;
		cin >> h;
		diff[i] = h - m*i;
		mp[diff[i]]++;
	}
	int cnt = 0;
	for (auto&v : mp) v.second = cnt++;
	vector<int> dp(n + 5, -1e18), tree(4 * n + 5, -1e18);
	diff[0] = mp[diff[0]];
	dp[0] = 0;
	update(tree, 1, 0, n, diff[0], dp[0]);
	for (int i = 1; i <= n; i++) {
		diff[i] = mp[diff[i]];
		dp[i] = 1 + query(tree, 1, 0, n, diff[i], n);
		update(tree, 1, 0, n, diff[i], dp[i]);
	}
	cout << n - *max_element(dp.begin(), dp.begin() + n + 1) << '\n';
	return 0;
}

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