#include <bits/stdc++.h>
using namespace std;
vector<int> get_lis(vector<int> v){
int n = (int)v.size();
if(n == 0) return {};
vector<int> lis;
vector<int> Last(n + 1 , -1) , p (n + 1 , -1);
for(int i = 0 ; i < n ; i++){
int val = v[i];
auto q = lower_bound(lis.begin(),lis.end() , val);
int idx = q - lis.begin();
if(q == lis.end()){
lis.emplace_back(val);
}
else{
*q = val;
}
Last[i] = (idx > 0 ? p[idx - 1] : -1);
p[idx] = i;
}
vector<int> ans;
int sz = (int)lis.size();
for(int i = p[sz - 1] ; i != -1 ; i = Last[i]){
ans.emplace_back(i);
}
reverse(ans.begin() , ans.end());
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n , x;
cin >> n >> x;
vector<int> v(n);
for(int i = 0 ; i < n ; i++){
cin >> v[i];
}
vector<int> ans = get_lis(v);
int best = (int)ans.size();
for(int i = 1 ; i < (int)ans.size() ; i++){
int l = ans[i - 1];
int r = ans[i];
vector<int> q;
for(int k = l + 1 ; k < r ; k++){
q.emplace_back(v[k]);
}
vector<int> now_t = get_lis(q);
if(now_t.empty()) continue;
int a = now_t[0] , b = now_t[(int)now_t.size()-1];
int d = abs(q[b] - v[r]) + (q[b] >= v[r] ? 1 : -1);
if(!(d >= -x && d <= x)) continue;
int left = 0 , right = (int)now_t.size() - 1;
int best_id = 0;
while(left <= right){
int mid = left + (right - left) / 2;
if(q[now_t[mid]] - d >= q[a]){
best_id = mid;
right = mid - 1;
}
else{
left = mid + 1;
}
}
int new_ans = (int)ans.size() + (int)now_t.size() - best_id;
best = max(best , new_ans);
left = 0 , right = (int)now_t.size() - 1;
int new_d = abs(q[a] - v[l]) + (q[a] >= v[l] ? -1 : 1);
int new_id = (int)now_t.size() - 1;
if(!(new_d >= -x && new_d <= x)) continue;
while(left <= right){
int mid = left + (right - left) / 2;
if(q[now_t[mid]] - new_d <= q[b]){
new_id = mid;
left = mid + 1;
}
else right = mid - 1;
}
best = max(best , (int)ans.size() + new_id + 1);
}
int r = ans[0];
vector<int> q;
for(int i = 0 ; i < r ; i++) {
q.emplace_back(v[i]);
}
vector<int> take = get_lis(q);
if(!take.empty()){
int idx_last = take[(int)take.size()- 1];
int diff = - v[r] + q[idx_last] + (q[idx_last] >= v[r] ? 1 : -1);
if(diff >= -x && diff <= x) best = max(best , (int)ans.size() + (int)take.size());
}
vector<int> Last;
for(int i = ans[(int)ans.size() - 1] + 1 ; i < n ; i++){
Last.emplace_back(v[i]);
}
vector<int> get = get_lis(Last);
if(!get.empty()){
int j = get[0];
int val = v[ans[(int)ans.size()-1]];
// int new_diff = v[ans[(int)ans.size()-1]] - Last[j] + 1;
int new_diff = abs(Last[j] - val) + (Last[j] >= val ? -1 : 1);
if(new_diff >= -x && new_diff <= x) best = max(best , (int)ans.size() + (int)get.size());
}
cout << best << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
308 KB |
Output is correct |
12 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
308 KB |
Output is correct |
12 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
5384 KB |
Output is correct |
2 |
Correct |
40 ms |
5324 KB |
Output is correct |
3 |
Correct |
37 ms |
5320 KB |
Output is correct |
4 |
Correct |
37 ms |
5316 KB |
Output is correct |
5 |
Correct |
33 ms |
5788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
1532 KB |
Output is correct |
2 |
Correct |
10 ms |
1528 KB |
Output is correct |
3 |
Correct |
10 ms |
1596 KB |
Output is correct |
4 |
Correct |
9 ms |
1612 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
9 ms |
1612 KB |
Output is correct |
7 |
Incorrect |
9 ms |
1484 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
19 ms |
2864 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
308 KB |
Output is correct |
12 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |