#include <bits/stdc++.h>
using namespace std;
int n, x;
int a[200005], s[200005];
int suf[200005], pref[200005];
int Sol = 0;
void find_lis(int d[], int st, int dr, int sgn){
int L = 0;
memset(s, 0, sizeof(s));
for(int i = st; i != dr ; i += sgn){
a[i] = a[i] * sgn;
if(s[L] < a[i] || L == 0){
s[++L] = a[i];
d[i] = L;
}
else{
int l = 1, dr = L;
bool ok = true;
while(l <= dr){
int mij = (l + dr) / 2;
if(s[mij] == a[i]){
ok = false;
d[i] = mij;
break ;
}
if(s[mij] > a[i]) dr = mij - 1;
else l = mij + 1;
}
if(s[dr] == a[i]){
ok = false;
d[i] = dr;
}
if(!ok) continue ;
s[l] = a[i], d[i] = l;
}
}
Sol = max(Sol, L);
for(int i = 1; i <= n ; ++i) a[i] = a[i] * sgn;
}
struct node{
int val;
node *left, *right;
node(){
val = 0;
left = right = 0;
}
};
node *arb;
int query(int x, int y, int st = 1, int dr = 1e9, node *nod = arb){
if(nod == NULL) return 0;
if(x <= st && dr <= y) return nod->val;
int mij = (st + dr) / 2;
int a1 = 0, a2 = 0;
if(x <= mij) a1 = query(x, y, st, mij, nod->left);
if(mij + 1 <= y) a2 = query(x, y, mij + 1, dr, nod->right);
return max(a1, a2);
}
void update(int val, int pos, int st = 1, int dr = 1e9, node *nod = arb){
if(st == dr){
nod->val = val;
return ;
}
if(nod->left == NULL) nod->left = new node;
if(nod->right == NULL) nod->right = new node;
int mij = (st + dr) / 2;
if(pos <= mij){
update(val, pos, st, mij, nod->left);
}
else{
update(val, pos, mij + 1, dr, nod->right);
}
nod->val = max(nod->left->val, nod->right->val);
}
int main()
{
// freopen("1.in", "r", stdin);
scanf("%d%d", &n, &x);
for(int i = 1; i <= n ; ++i) scanf("%d", &a[i]);
find_lis(pref, 1, n + 1, 1);
find_lis(suf, n, 0, -1);
if(x == 0){
printf("%d", Sol);
return ;
}
arb = new node;
update(pref[1], a[1]);
for(int i = 1; i < n ; ++i){
int aux = suf[i + 1];
aux = aux + query(max(a[i + 1] - x + 1, 1), min(a[i + 1] + x - 1, 1000000000));
Sol = max(Sol, aux);
update(pref[i + 1], a[i + 1]);
}
arb = new node;
update(suf[n], a[n]);
for(int i = n; i > 1 ; --i){
int aux = pref[i - 1];
aux = aux + query(max(a[i - 1] - x + 1, 1), min(a[i - 1] + x - 1, 1000000000));
Sol = max(Sol, aux);
update(suf[i - 1], a[i - 1]);
}
printf("%d", Sol);
return 0;
}
Compilation message
glo.cpp: In function 'int main()':
glo.cpp:110:9: error: return-statement with no value, in function returning 'int' [-fpermissive]
return ;
^~~~~~
glo.cpp:101:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &x);
~~~~~^~~~~~~~~~~~~~~~
glo.cpp:103:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 1; i <= n ; ++i) scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
