#include <iostream>
#include <set>
using namespace std;
int n, x;
int nums[200001];
int flipped_nums[200001];
int lis[200001];
int dp1[200001];
int dp2[200001];
const int INF = 1e9 + 5;
int binary_search(int key){
int lo = 1;
int hi = n;
int ans = 0;
while (lo <= hi){
int mid = (lo + hi)/2;
if (lis[mid] < key){
ans = mid;
lo = mid + 1;
}
else{
hi = mid - 1;
}
}
return ans;
}
int main(){
cin >> n >> x;
for (int i = 1;i <= n;i++){
cin >> nums[i];
flipped_nums[n - i + 1] = INF - nums[i];
}
int ans = 0;
for (int j = 1;j <= n;j++){
lis[j] = INF;
}
for (int j = 1;j <= n;j++) {
int key = nums[j];
int index = binary_search(key);
lis[index + 1] = key;
if (index + 1 > ans) {
ans = index + 1;
}
dp1[j] = index + 1;
}
for (int j = 1;j <= n;j++){
lis[j] = INF;
}
for (int j = 1;j <= n;j++) {
int key = flipped_nums[j];
int index = binary_search(key);
lis[index + 1] = key;
if (index + 1 > ans) {
ans = index + 1;
}
dp2[j] = index + 1;
}
set<int> s;
for (int i = 1;i <= n;i++){
s.insert(dp2[i]);
}
for (int i = 1;i < n;i++){
s.erase(dp2[i]);
int sum = dp1[i] + *s.upper_bound(nums[i] - x);
if (sum > ans){
ans = sum;
}
}
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
84 ms |
6260 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
21 ms |
3412 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
40 ms |
4184 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |