#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=0;
for(int i=n-1;i>=0;i--) {
auto it=lower_bound(lds.begin(), lds.end(), -t[i]-x);
int pos;
auto it2=lower_bound(lds.begin(), lds.end(), -t[i]);
if(it2==lds.end()) pos=lds.size();
else pos=it2-lds.begin()+1;
ans=max(ans, pos+len[i]-1);
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
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
184 ms |
3868 KB |
Output is correct |
2 |
Correct |
188 ms |
4088 KB |
Output is correct |
3 |
Correct |
190 ms |
3832 KB |
Output is correct |
4 |
Correct |
185 ms |
3832 KB |
Output is correct |
5 |
Correct |
122 ms |
4208 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
47 ms |
1144 KB |
Output is correct |
2 |
Correct |
48 ms |
1196 KB |
Output is correct |
3 |
Correct |
47 ms |
1144 KB |
Output is correct |
4 |
Correct |
33 ms |
1272 KB |
Output is correct |
5 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
89 ms |
2168 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |