#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];
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 |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
21 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
69 ms |
5460 KB |
Output is correct |
2 |
Correct |
70 ms |
5404 KB |
Output is correct |
3 |
Correct |
71 ms |
5456 KB |
Output is correct |
4 |
Correct |
69 ms |
5324 KB |
Output is correct |
5 |
Correct |
40 ms |
5076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
1540 KB |
Output is correct |
2 |
Correct |
17 ms |
1548 KB |
Output is correct |
3 |
Correct |
19 ms |
1628 KB |
Output is correct |
4 |
Correct |
10 ms |
1580 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
10 ms |
1604 KB |
Output is correct |
7 |
Correct |
16 ms |
1628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
3156 KB |
Output is correct |
2 |
Correct |
34 ms |
2896 KB |
Output is correct |
3 |
Correct |
87 ms |
5492 KB |
Output is correct |
4 |
Correct |
39 ms |
5068 KB |
Output is correct |
5 |
Correct |
20 ms |
2776 KB |
Output is correct |
6 |
Correct |
51 ms |
5592 KB |
Output is correct |
7 |
Correct |
52 ms |
5480 KB |
Output is correct |
8 |
Correct |
37 ms |
2896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
21 |
Halted |
0 ms |
0 KB |
- |