Submission #422039

#	Time	Username	Problem	Language	Result	Execution time	Memory
422039		rqi	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	115 ms	5848 KiB

triusis

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

typedef long long ll;
typedef vector<ll> vl;

#define pb push_back
#define bk back()
#define sz(x) (int)(x).size()

const int mx = 200005;
int N, M;
ll a[mx];
int main(){
	cin >> N >> M;
	for(int i = 1; i <= N; i++){
		cin >> a[i];
	}
	for(int i = 1; i <= N; i++){
		a[i]-=ll(i)*ll(M);
	}
	vl dp = vl{0};
	for(int i = 1; i <= N; i++){
		if(a[i] > 0) continue;
		if(a[i] <= dp.bk){
			dp.pb(a[i]);
			continue;
		}
		int lo = 0;
		int hi = sz(dp)-1;
		while(lo < hi){
			int mid = (lo+hi)/2+1;
			if(dp[mid] >= a[i]){
				lo = mid;
			}
			else{
				hi = mid-1;
			}
		}

		dp[lo+1] = a[i];
	}

	int ans = N-(sz(dp)-1);
	cout << ans << "\n";
}

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