Submission #1268417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268417		hgia	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	49 ms	3524 KiB

triusis

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+1;
const int R=1e9+7;
int n,m,ans;
int a[N],dp[N],bit[N];
vector<int>nen;
void update(int pos,int val)
{
  for(int i=pos;i<N;i+=(i&-i))bit[i]=max(bit[i],val);
}
int get(int pos)
{
  int tmp=0;
  for(int i=pos;i;i-=(i&-i))tmp=max(tmp,bit[i]);
  return tmp;
}
main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // freopen("VISIT.inp","r",stdin);
    // freopen("VISIT.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
      int x;
      cin>>x;
      a[i]=m*i-x;
      nen.push_back(a[i]);
    }
    nen.push_back(0);
    sort(nen.begin(),nen.end());
    nen.erase(unique(nen.begin(),nen.end()),nen.end());
    ans=1e9;
    for(int i=0;i<=n;i++)
    {
      a[i]=lower_bound(nen.begin(),nen.end(),a[i])-nen.begin()+1;
      if(nen[a[i]-1]<0)continue;
      dp[i]=get(a[i])+1;
      update(a[i],dp[i]);
      ans=min(ans,n-dp[i]+1);
    }
    cout<<ans;
    return 0;
}

Compilation message (stderr)

triusis.cpp:18:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   18 | main()
      | ^~~~

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