#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define sz size()
using namespace std;
[[maybe_unused]]const int e6=1e6;
[[maybe_unused]]const int e7=1e7;
[[maybe_unused]]const int e8=1e8;
[[maybe_unused]]const int e9=1e9;
inline int rd(){
int num;cin>>num;
return num;
}
inline ll rdll(){
ll num;cin>>num;
return num;
}
[[maybe_unused]]const ll inf=1e18+7;
[[maybe_unused]]const ll MOD=1e9+7;
[[maybe_unused]]const int N=1e6+3;
int a[N];
int bl[N];
void code(){
int n,k;cin>>n>>k;
vector<pair<int,int>>v;
for(int i=1;i<=n;i++){
cin>>a[i];
v.push_back({a[i],i});
}
sort(v.begin(),v.end());
for(int i=0;i<(int)v.sz;i++)bl[v[i].S]=i/k;
vector<int>b={bl[1]};
for(int i=2;i<=n;i++){
if(b.back()<=bl[i])b.push_back(bl[i]);
else{
auto it=upper_bound(b.begin(),b.end(),bl[i]);
if(it==b.end())continue;
*it=bl[i];
}
}
cout<<n-(int)b.sz;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int tt=1;
// cin>>tt;
while(tt--)code(),cout<<"\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |