Submission #1158886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158886		AlgorithmWarrior	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	59 ms	2320 KiB

triusis

#include <bits/stdc++.h>

using namespace std;

int const MAX=2e5+5;
int n,m;
int v[MAX];

void read(){
    cin>>n>>m;
    int i;
    for(i=1;i<=n;++i)
        cin>>v[i];
    for(i=n;i>=0;--i)
        v[i]+=(n-i)*m;
}

void rev(int v[],int n){
    int st=0,dr=n;
    while(st<dr){
        swap(v[st],v[dr]);
        ++st;
        --dr;
    }
}

int lis(){
    vector<int>subset;
    int i;
    for(i=0;i<n;++i){
        auto it=upper_bound(subset.begin(),subset.end(),v[i]);
        if(it==subset.end())
            subset.push_back(v[i]);
        else{
            int pos=it-subset.begin();
            subset[pos]=v[i];
        }
    }
    return upper_bound(subset.begin(),subset.end(),v[n])-subset.begin();
}

int main()
{
    read();
    rev(v,n);
    cout<<n-lis();
    return 0;
}

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