Submission #1322443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1322443		aaaaaaaa	Rabbit Carrot (LMIO19_triusis)	C++20	0 / 100	34 ms	504 KiB

triusis

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()

int lds(vector<int> x){
	int n = (int) x.size();
	vector<int> ord, seg((n + 5) * 2, 0);
	for(int i = 0; i < n; ++i){
		ord.push_back(x[i]);
	}
	sort(all(ord));
	ord.erase(unique(all(ord)), ord.end());
	auto pos = [&](int x) -> int {
		return lower_bound(all(ord), x) - ord.begin();
	};
	auto update = [&](int idx, int val) -> void {
		idx += n;
		seg[idx] = max(seg[idx], val);
		while(idx > 1){
			idx >>= 1;
			seg[idx] = max(seg[idx << 1], seg[idx << 1 | 1]);
		}
	};
	auto query = [&](int l, int r) -> int {
		if(l > r) return 0;
		l += n, r += n;
		int ans = 0;
		while(l <= r){
			if(l & 1) ans = max(ans, seg[l ++]);
			if(r & 1 ^ 1) ans = max(ans, seg[r --]);
			l >>= 1, r >>= 1;
		}
		return ans;
	};
	for(auto it : x){
		int i = pos(it);
		update(i, query(i, n - 1) + 1);
	}
	return *max_element(all(seg));
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr); cout.tie(nullptr);
	int n, m;
	cin >> n >> m;
	vector<int> ar(n + 1), dp(n + 5, 1);
	for(int i = 1; i <= n; ++i){
		cin >> ar[i];
		ar[i] -= m * i;
	}
	for(int i = 1; i <= n; ++i){
		for(int j = i - 1; j >= 1; --j){
			if(ar[j] >= ar[i]) dp[i] = max(dp[i], dp[j] + 1);
		}
	}
	cout << n - *max_element(all(dp)) << "\n";
	return 0;
}

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