This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pr pair<int, int>
#define prr pair<pr, int>
#define f first
#define s second
#define pr pair<int, int>
#define pb push_back
const int ndim=2e5+1;
vector<int> par(ndim);
vector<int> psize(ndim);
int main(){
int n, m; cin>>n>>m;
vector<int> d(n+1);
for (int i=1; i<=n; i++) cin>>d[i];
d[0]=0;
multiset<pr> st;
vector<int> par(n+1);
for (int i=0; i<=n; i++) par[i]=i;
st.insert({d[0], 0});
for (int i=1; i<=n; i++){
auto it=st.upper_bound({d[i], i});
if(it==st.end()) {
it--; par[i]=it->s;
st.insert({d[i], i});
}
else{
st.erase(it);
st.insert({d[i], i});
it=st.lower_bound({d[i], i});
it--;
par[i]=it->s;
}
}
vector<int> dp(n+1, 0);
vector<int> ds(n+1);
ds[0]=d[0];
int res=0;
for (int i=1; i<=n; i++){
if(d[i]-ds[i-1]>m || d[i]-ds[par[i]]>m*(i-par[i])){
//cout<<" i= "<<i<<endl;
//cout<<" d[i]-ds[i-1]/m/ d[i]-ds[par[i]]/m*(i-par[i]="<<d[i]-ds[i-1]<<" "<<m<<" "<< d[i]-ds[par[i]]<<" "<<m*(i-par[i])<<endl;
ds[i]=min(ds[i-1]+m, m*(i-par[i])+ds[par[i]]);
res++;
}
else ds[i]=d[i];
}
cout<<res<<endl;
}
# | 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... |