제출 #1190336

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190336		boclobanchat	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	54 ms	4324 KiB

triusis

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
long long A[MAXN],val[MAXN];
int fen[MAXN];
void update(int i,int n,int val) { for(;i<=n;i+=i&-i) fen[i]=max(fen[i],val); }
int get(int i) { int ans=-1e9;for(;i;i-=i&-i) ans=max(ans,fen[i]);return ans; }
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
    	cin>>A[i];
    	A[i]=m*i-A[i],val[i]=A[i];
	}
	val[n+1]=0;
	sort(val+1,val+n+2);
	for(int i=1;i<=n+1;i++) fen[i]=-1e9;
	int p=lower_bound(val+1,val+n+2,0)-val;
	update(p,n+1,0);
	for(int i=1;i<=n;i++)
	{
		A[i]=lower_bound(val+1,val+n+2,A[i])-val;
		update(A[i],n+1,get(A[i])+1);
	}
	cout<<n-get(n+1);
}

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