#include <bits/stdc++.h>
using namespace std;
#define int long long
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;
}
// 5 8 9 12 1 2 3 14 19 20 21 15 16 17 18
int get_down_right(vector<int> v , vector<int> q , vector<int> now_t , int l , int r , int x){
int Max = q[now_t[(int)now_t.size()-1]];
int diff = Max - (v[r] - 1);
int left = 0 , right = (int)now_t.size() - 1;
int best_id = (int)now_t.size();
if(diff > x) return 0;
while(left <= right){
int mid = left + (right - left) / 2;
int val = q[now_t[mid]] - diff;
if(val > v[l]){
best_id = min(best_id , mid);
right = mid - 1;
}
else left = mid + 1;
}
return (int)now_t.size() - best_id;
}
int get_up_right(vector<int> v , vector<int> q , vector<int> now_t , int l , int r , int x){
int Max = q[now_t[(int)now_t.size()-1]];
int diff = v[r] - Max - 1;
if(diff > x) return 0;
int left = 0 , right = (int)now_t.size() - 1;
int best_id = (int)now_t.size();
while(left <= right){
int mid = left + (right - left) / 2;
int val = q[now_t[mid]] + diff;
if(val > v[l]){
best_id = min(best_id , mid);
right = mid - 1;
}
else left = mid + 1;
}
return (int)now_t.size() - best_id;
}
int get_down_left(vector<int> v , vector<int> q , vector<int> now_t , int l , int r , int x){
int Min = q[now_t[0]];
int diff = Min - (v[l] + 1);
if(diff > x) return 0;
int left = 0 , right = (int)now_t.size() - 1;
int best_id = -1;
while(left <= right){
int mid = left + (right - left) / 2;
int val = q[now_t[mid]] - diff;
if(val < v[r]){
best_id = max(best_id , mid);
left = mid + 1;
}
else right = mid - 1;
}
return best_id + 1;
}
int get_up_left(vector<int> v , vector<int> q , vector<int> now_t , int l , int r , int x){
int Min = q[now_t[0]];
int diff = v[l] - Min + 1;
if(abs(diff) > x) return 0;
int left = 0 , right = (int)now_t.size() - 1;
int best_id = -1;
while(left <= right){
int mid = left + (right - left) / 2;
int val = q[now_t[mid]] + diff;
if(val < v[r]){
best_id = max(best_id , mid);
left = mid + 1;
}
else right = mid - 1;
}
return best_id + 1;
}
int deb(vector<int> v , vector<int> ans , int x){
int f_id = ans[0];
vector<int> q;
for(int i = 0 ; i < f_id ; i++){
q.emplace_back(v[i] - x);
}
vector<int> Lis = get_lis(q);
if(Lis.empty()) return 0;
int now_t = 0;
for(int i = 0 ; i < (int)Lis.size() ; i++){
int cur = q[Lis[i]];
if(cur < v[f_id]) now_t++;
else break;
}
return now_t;
}
int fin(vector<int> v , vector<int> ans , int x){
int n = (int)v.size();
int Last_id = ans[(int)ans.size() - 1];
vector<int> q;
for(int i = Last_id + 1 ; i < n ; i++){
q.emplace_back(v[i] + x);
}
vector<int> Lis = get_lis(q);
if(Lis.empty()) return 0;
int now_t = 0;
for(int i = 0 ; i < (int)Lis.size() ; i++){
int cur = q[Lis[i]];
if(cur > v[Last_id]) now_t++;
}
return now_t;
}
int32_t 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);
int new_ans = 0;
if(now_t.empty()) continue;
int Max = q[now_t[(int)now_t.size()-1]];
int Min = q[now_t[0]];
if(Max <= v[r]){
//assert(Max <= v[l]);
new_ans = max(get_up_left(v , q , now_t , l , r , x) , get_up_right(v , q , now_t , l , r , x));
}
else if(Min >= v[l]){
//assert(Min >= v[r]);
new_ans = max(get_down_left(v , q , now_t , l , r , x) , get_down_right(v , q , now_t , l , r , x));
}
best = max(best , (int)ans.size() + new_ans);
}
vector<int> here;
for(int i = 0 ; i < (int)ans.size(); i++){
here.emplace_back(v[ans[i]]);
}
best = max(best , max(deb(v , ans , x) , fin(v , ans , x)) + (int)ans.size());
cout << best << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
162 ms |
6708 KB |
Output is correct |
| 2 |
Correct |
162 ms |
6948 KB |
Output is correct |
| 3 |
Correct |
185 ms |
6976 KB |
Output is correct |
| 4 |
Correct |
175 ms |
6892 KB |
Output is correct |
| 5 |
Execution timed out |
2081 ms |
8904 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
1948 KB |
Output is correct |
| 2 |
Correct |
31 ms |
1904 KB |
Output is correct |
| 3 |
Correct |
35 ms |
1904 KB |
Output is correct |
| 4 |
Execution timed out |
2084 ms |
2428 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
3644 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 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
