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>
#define mp make_pair
using namespace std;
const int N=2e5+10;
int t[N];
vector<int> fv,bv;
stack<pair<int,pair<int,int> > > st;
int main(){
int n,m;
cin>>n >>m;
for(int i=1;i<=n;i++) cin>>t[i];
if(n==1){
cout<<1;
return 0;
}
bv.push_back(t[n]);
for(int i=n-1;i>=1;i--){
int ind;
if(t[i]<bv.back()){
bv.push_back(t[i]);
st.push(mp(1,mp(0,0)));
continue;
}
ind=lower_bound(bv.begin(),bv.end(),t[i],greater<int>())-bv.begin();
st.push(mp(0,mp(ind,bv[ind])));
bv[ind]=t[i];
}
int ans=bv.size();
if(st.top().first==1) bv.pop_back();
else bv[st.top().second.first]=st.top().second.second;
st.pop();
for(int i=1;i<=n-1;i++){
int ind;
if(fv.empty()) fv.push_back(t[i]);
else{
if(t[i]>fv.back()) fv.push_back(t[i]);
else{
ind=lower_bound(fv.begin(),fv.end(),t[i])-fv.begin();
fv[ind]=t[i];
}
}
ind=lower_bound(bv.begin(),bv.end(),fv.back()-m,greater<int>())-bv.begin();
ans=max(ans,(int)fv.size()+ind);
if(st.empty()) break;
if(st.top().first==1) bv.pop_back();
else bv[st.top().second.first]=st.top().second.second;
st.pop();
}
cout<<ans;
}
# | 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... |