#include <iostream>
#include <map>
using namespace std;
int n, x;
int 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];
}
int ans = 0;
for (int i = 1;i <= n;i++){
lis[i] = INF;
}
for (int i = 1;i <= n;i++) {
int key = nums[i];
int index = binary_search(key);
lis[index + 1] = key;
if (index + 1 > ans) {
ans = index + 1;
}
dp1[i] = index + 1;
}
for (int i = 1;i <= n;i++){
lis[i] = INF;
}
for (int i = n;i >= 1;i--) {
int key = nums[i];
int index = binary_search(key);
lis[index + 1] = key;
if (index + 1 > ans) {
ans = index + 1;
}
dp2[i] = index + 1;
}
map<int, int> m;
for (int i = 1;i <= n;i++){
m[dp2[i]] += 1;
}
for (int i = 1;i < n;i++){
m[dp2[i]] -= 1;
if (m[dp2[i]] == 0){
m.erase(dp2[i]);
}
// cout << dp1[i] << ' ' << m.upper_bound(nums[i] - x)->first << '\n';
int sum = dp1[i] + m.upper_bound(nums[i] - x)->first;
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 |
115 ms |
3408 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
22 ms |
2652 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
44 ms |
2900 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 |
- |