Submission #715590

#	Time	Username	Problem	Language	Result	Execution time	Memory
715590		amunduzbaev	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	170 ms	13320 KiB

triusis

#include "bits/stdc++.h"
using namespace std;

#define ar array
typedef long long ll;
#define int ll

const int N = 2e5 + 5;
int a[N], dp[N];

struct ST{
	int tree[N << 2];
	ST(){
		memset(tree, 200, sizeof tree);
	}
	
	void set(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) { tree[x] = max(tree[x], v); return; }
		int m = (lx + rx) >> 1;
		if(i <= m) set(i, v, lx, m, x << 1);
		else set(i, v, m + 1, rx, x << 1 | 1);
		tree[x] = max(tree[x << 1], tree[x << 1 | 1]);
	}
	
	int get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return -N;
		if(lx >= l && rx <= r) return tree[x];
		int m = (lx + rx) >> 1;
		return max(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
	}
}tree;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);

	int n, m; cin >> n >> m;
	vector<int> t;
	t.push_back(0);
	for(int i=1;i<=n;i++){
		cin >> a[i];
		a[i] -= i * m;
		t.push_back(a[i]);
	}
	sort(t.begin(), t.end());
	t.erase(unique(t.begin(), t.end()), t.end());
	{
		int j = lower_bound(t.begin(), t.end(), a[0]) - t.begin();
		tree.set(j, 0);
	}
	for(int i=1;i<=n;i++){
		int j = lower_bound(t.begin(), t.end(), a[i]) - t.begin();
		dp[i] = tree.get(j, n) + 1;
		tree.set(j, dp[i]);
	}
	
	cout<<n - tree.get(0, n)<<"\n";
}

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