#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define nl endl
#define loop(i,a,b) for(ll i=a;i<b;i++)
#define rloop(i,a,b) for(ll i=b;i>=a;i--)
#define cy cout<<"YES"<<endl;
#define cn cout<<"NO"<<endl;
#define cm cout<<-1<<endl
#define vl vector<ll>
#define vchar vector<char>
#define vvll vector<vector<ll>>
#define vvcr vector<vchar>
#define deb(x) cout<<#x<<" "<<x<<endl;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
using namespace std;
const ll MOD=1e9+7;
ll binepow(ll a,ll b,ll mod=-1){
if(b==0){
return 1ll;
}
if(mod!=-1){
ll k=binepow(a,b/2,mod);
if(b%2==0){
return (k*k)%mod;
}
else{
return (((k*a)%mod)*k)%mod;
}
}
else{
ll k=binepow(a,b/2,mod);
if(b%2==0){
return (k*k);
}
else{
return k*k*a;
}
}
}
////////////////////////////////////////////////////////
void solve(){
ll n,m;
cin>>n>>m;
vl a(n+1);
loop(i,1,n+1){
cin>>a[i];
}
a[0]=-(n+1)*m;
vl big(n+1,0);
ll tot=0;
loop(i,1,n+1){
ll lo=1;ll hi=n;
ll k=1;
while(lo<=hi){
ll mid=(lo+hi)/2;
if(a[big[mid]]+m*(i-big[mid])>=a[i]){
k=max(mid+1,k);
lo=mid+1;
}
else{
hi=mid-1;
}
}
// deb(k)
if(k!=1){
if(a[big[k]]+m*(i-big[k])<a[i]){
big[k]=i;
}
tot=max(tot,k);
}
else if(k==1 && a[i]<=(i*m)){
if(a[big[k]]+m*(i-big[k])<a[i]){
big[k]=i;
}
tot=max(tot,k);
}
}
cout<<n-tot<<endl;
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
// ll t;
// cin>>t;
// while(t--){
// solve();
// }
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
