#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pi pair<ll,ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define alll(x) ((x).begin()+1), (x).end()
#define clean(v) (v).resize(distance((v).begin(), unique(all(v))));
#define yes cout<<"Yes"<<endl;
#define no cout<<"No"<<endl;
#define mod mod
#define endl '\n'
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353;
void io() {
ios::sync_with_stdio(false);
cin.tie(NULL);
}
template<class T>
bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<class T>
bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
void nop() {
cout << -1 << endl;
return;
}
template<class T> struct Seg { // comb(ID,b) = b
const T ID = 0; T comb(T a, T b) { return max(a , b); }
int n; vector<T> seg;
void init(int _n) { n = _n; seg.assign(2*n,ID); }
void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
void upd(int p, T val) { // set val at position p
seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }
T query(int l, int r) { // sum on interval [l, r]
T ra = ID, rb = ID;
for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
if (l&1) ra = comb(ra,seg[l++]);
if (r&1) rb = comb(seg[--r],rb);
}
return comb(ra,rb);
}
};
vector<int> v ;
int get(int x){return lower_bound(all(v) , x) - v.begin() + 1; }
void solve() {
int n , m ; cin>>n>>m ;
vector<int> a(n+1) , dp(n+1) ;
for(int i = 1 ; i<=n ; i++){
cin>>a[i] ;
a[i] = i*m - a[i] ;
v.pb(a[i]) ;
}
sort(all(v)) ;
Seg<int> st ; st.init(n+5) ;
for(int i = 1 ; i<=n ; i++){
int idx = get(a[i]) ;
dp[i] = max(dp[i-1] , st.query(1 , idx) + 1) ;
st.upd(idx , dp[i]) ;
}
cout<<n - dp[n]<<endl;
}
int main() {
io();
ll tt = 1;
//cin>>tt ;
while (tt--) {
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
