Submission #253204

#	Time	Username	Problem	Language	Result	Execution time	Memory
253204		nandonathaniel	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	127 ms	13032 KiB

triusis

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MAXN=200005;
int MAX,a[MAXN],bit[MAXN];
map<int,int> mp;

int query(int x){
	int ret=0;
	for(int i=x;i>0;i-=(i&-i)){
		ret=max(ret,bit[i]);
	}
	return ret;
}

void update(int x,int v){
	for(int i=x;i<=MAX;i+=(i&(-i))){
		bit[i]=max(bit[i],v);
	}
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n,m;
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> a[i];
		a[i]-=(i*m);
	}
	vector<pii> v;
	for(int i=0;i<=n;i++){
		if(a[i]>0)continue;
		v.push_back({-a[i],i});
	}
	for(auto isi : v)mp[isi.first];
	for(map<int,int>::iterator it=mp.begin();it!=mp.end();++it){
		MAX++;
		mp[it->first]=MAX;
	}
	int ans=0;
	for(auto isi : v){
		int dp=query(mp[isi.first])+1;
		update(mp[isi.first],dp);
		ans=max(ans,dp);
	}
	cout << n+1-ans << endl;
	return 0;
}

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