Submission #521337

#	Time	Username	Problem	Language	Result	Execution time	Memory
521337		dsyz	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	124 ms	36792 KiB

triusis

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
struct node {
	node *l, *r;
	ll s,e,m,v;
	node(ll _s,ll _e){
		s = _s;
		e = _e;
		m = (s + e) / 2;
		v = 0;
		if(s != e){
			l = new node(s,m);
			r = new node(m + 1,e);
		}
	}
	void update(ll x,ll val){
		if(s == e){
			 v = val;
			 return;
		}
		else if(x > m) r -> update(x,val);
		if(x <= m) l -> update(x,val);
		v = max(l -> v,r -> v);
	}
	long long rmq(ll S,ll E){
		if(s == S && e == E) return v;
		else if(S > m) return r -> rmq(S,E);
		else if(E <= m) return l -> rmq(S,E);
		else return max(l -> rmq(S,m),r -> rmq(m + 1,E));
	}	
} *root;
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,M;
	cin>>N>>M;
	root = new node(0,N + 5);
	ll arr[N];
	for(ll i = 0;i < N;i++){
		cin>>arr[i];
	}
	ll num[N];
	for(ll i = 0;i < N;i++){
		num[i] = 1;
	}
	for(ll i = 0;i < N;i++){
		if(arr[i] > (i + 1) * M){
			num[i] = 0;
		}
	}
	vector<pair<ll,ll> > v;
	for(ll i = 0;i < N;i++){
		v.push_back(make_pair(min(arr[i],(i + 1) * M) - (i * M),-1 * i));
	}
	sort(v.begin(),v.end(),greater<pair<ll,ll> >());
	ll index[N];
	memset(index,0,sizeof(index));
	for(ll i = 0;i < N;i++){
		index[-1 * v[i].second] = i;	
	}
	ll sum = 0;
	ll dp[N];
	memset(dp,0,sizeof(dp));	
	for(ll i = 0;i < N;i++){
		ll a = root -> rmq(0,index[i]);
		dp[i] = a + num[i];
		sum = max(sum,dp[i]);
		root -> update(index[i],dp[i]);
	}
	cout<<N - sum<<'\n';
}

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