#include <bits/stdc++.h>
using namespace std;
#define MAXN 200200
int a[MAXN];
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
for(int i=1;i<=n;i++) cin >> a[i];
int ans=0;
vector<pair<int, int>> vec;
for(int i=1;i<=n;i++) {
int mx=i*m;
a[i]-=mx;
if(a[i]>0) {
ans++;
continue;
}
a[i]*=-1;
vec.push_back({a[i], i});
}
vector<pair<int, int>> lens;
for(auto x : vec) {
auto p = lower_bound(lens.begin(), lens.end(), x);
if(p==lens.end()) lens.push_back(x);
else *p=x;
}
ans+=vec.size()-lens.size();
cout << ans << endl;
return 0;
}
# | 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... |