#include <bits/stdc++.h>
using namespace std;
int n, x, idx, arr[200010], pre[200010], ans;
vector<int> dp;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> x;
for(int i=1; i<=n; i++) {
cin >> arr[i];
idx = lower_bound(dp.begin(), dp.end(), arr[i]) - dp.begin();
if(idx == dp.size()) dp.push_back(arr[i]);
else dp[idx] = arr[i];
pre[i] = dp.size()+1;
}
ans = pre[n];
dp.clear();
for(int i=n-1; i>=0; i--) {
idx = lower_bound(dp.begin(), dp.end(), -arr[i]+x) - dp.begin();
ans = max(ans, pre[i] + idx);
idx = lower_bound(dp.begin(), dp.end(), -arr[i]) - dp.begin();
if(idx == dp.size()) dp.push_back(-arr[i]);
else dp[idx] = -arr[i];
}
cout << ans;
return 0;
}
Compilation message
glo.cpp: In function 'int main()':
glo.cpp:14:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | if(idx == dp.size()) dp.push_back(arr[i]);
| ~~~~^~~~~~~~~~~~
glo.cpp:24:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | if(idx == dp.size()) dp.push_back(-arr[i]);
| ~~~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
44 ms |
3688 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
11 ms |
1116 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
18 ms |
2140 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |