#include<bits/stdc++.h>
using namespace std;
int main() {
int n,x;
cin>>n>>x;
vector<int> t(n);
for(int i=0;i<n;++i) {
cin>>t[i];
}
vector<int> len(n);
vector<int> lis;
for(int i=0;i<n;++i) {
auto it=lower_bound(lis.begin(), lis.end(), t[i]);
if(it==lis.end()) {
lis.push_back(t[i]);
len[i]=lis.size();
}else {
*it=t[i];
len[i]=it-lis.begin()+1;
}
}
/*for(auto i:len) {
cerr<<i<<" ";
}cerr<<"\n";*/
vector<int> lds;
int ans=lis.size();
for(int i=n-1;i>=0;i--) {
int pos;
auto it2=lower_bound(lds.begin(), lds.end(), -t[i]-1);
if(it2==lds.end()) pos=lds.size();
else pos=it2-lds.begin()+1;
ans=max(ans, pos+len[i]);
auto it=lower_bound(lds.begin(), lds.end(), -t[i]-x);
if(it==lds.end()) {
lds.push_back(-t[i]-x);
}else {
*it=-t[i]-x;
}
}
cout<<ans<<"\n";
return 0;
}
/*
8 10
7 3 5 12 2 7 3 4
3 1
1 2 2
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
184 ms |
1952 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
46 ms |
660 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
88 ms |
1244 KB |
Output is correct |
2 |
Correct |
90 ms |
2020 KB |
Output is correct |
3 |
Correct |
176 ms |
3824 KB |
Output is correct |
4 |
Correct |
120 ms |
4204 KB |
Output is correct |
5 |
Correct |
61 ms |
2292 KB |
Output is correct |
6 |
Correct |
115 ms |
4152 KB |
Output is correct |
7 |
Correct |
157 ms |
4872 KB |
Output is correct |
8 |
Correct |
85 ms |
2272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |