#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;
const int inf=1e9;
struct ST{
struct node{
int l,r,val;
};
node tree[30*MAXN];
int num;
void init(){
num=1;
tree[num]={0,0,0};
}
void addnode(){
num++;
tree[num]={0,0,0};
}
void check(int v){
if(tree[v].l==0){
addnode(); tree[v].l=num;
}
if(tree[v].r==0){
addnode(); tree[v].r=num;
}
}
void update(int v,long long l,long long r,int pos,int val){
if(l==r){
tree[v].val=max(tree[v].val,val);
}else{
long long tt=(l+r)/2;
check(v);
if(pos<=tt)update(tree[v].l,l,tt,pos,val);
else update(tree[v].r,tt+1,r,pos,val);
tree[v].val=max(tree[tree[v].l].val,tree[tree[v].r].val);
}
}
int getmax(int v,long long l,long long r,long long ll,long long rr){
if(ll>rr or v==0)return 0;
if(l==ll and r==rr){
return tree[v].val;
}else{
long long tt=(l+r)/2;
return max( getmax(tree[v].l,l,tt,ll,min(tt,rr)) , getmax(tree[v].r,tt+1,r,max(tt+1,ll),rr) );
}
}
}seg[3];
int n,a[MAXN],ans,x;
int dp[MAXN][3];
int solve(int d){
seg[0].init();
seg[1].init();
seg[2].init();
int res=0;
for(int i=1;i<=n;i++){
dp[i][0]=seg[0].getmax(1,0,2*inf,0,a[i]-1)+1;
dp[i][1]=max(seg[1].getmax(1,0,2*inf,0,a[i]-1)+1 , seg[0].getmax(1,0,2*inf,0,a[i]+d-1)+1);
dp[i][2]=max(seg[2].getmax(1,0,2*inf,0,a[i]-1)+1 , seg[1].getmax(1,0,2*inf,0,a[i]-d-1)+1);
seg[0].update(1,0,2*inf,a[i],dp[i][0]);
seg[1].update(1,0,2*inf,a[i],dp[i][1]);
seg[2].update(1,0,2*inf,a[i],dp[i][2]);
res=max(res,max(dp[i][0],max(dp[i][1],dp[i][2])));
}
return res;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>x;
for(int i=1;i<=n;i++){
cin>>a[i];
}
if(n<=1000){
unordered_set<int> w;
w.insert(0);
for(int i=1;i<=n;i++){
for(int f=i+1;f<=n;f++){
if(a[i]-a[f]+1>=-x and a[i]-a[f]+1<=x){
w.insert(a[i]-a[f]+1);
}
if(a[i]-a[f]-1>=-x and a[i]-a[f]-1<=x){
w.insert(a[i]-a[f]-1);
}
}
}
for(int i:w){
ans=max(ans,solve(i));
}
cout<<ans<<"\n";
return 0;
long long l=0,r=w.size()-1,lt,rt;
while(l+20<r){
lt=l+(r-l+1)/3;
rt=r-(r-l+1)/3;
int ls=solve(w[lt]);
int rs=solve(w[rt]);
if(ls>rs)l=lt;
else if(rs>ls)r=rt;
else{
break;
}
}
for(int d=l;d<=r;d++){
ans=max(ans,solve(w[d]));
}
cout<<ans<<"\n";
return 0;
}
long long l=-x,r=x,lt,rt;
while(l+20<r){
lt=l+(r-l+1)/3;
rt=r-(r-l+1)/3;
int ls=solve(lt);
int rs=solve(rt);
if(ls>rs)l=lt;
else if(rs>ls)r=rt;
else{
break;
}
}
for(int d=l;d<=r;d++){
ans=max(ans,solve(d));
}
cout<<ans<<"\n";
return 0;
}
Compilation message
glo.cpp: In function 'int main()':
glo.cpp:124:18: error: no match for 'operator[]' (operand types are 'std::unordered_set<int>' and 'long long int')
124 | int ls=solve(w[lt]);
| ^
glo.cpp:125:18: error: no match for 'operator[]' (operand types are 'std::unordered_set<int>' and 'long long int')
125 | int rs=solve(w[rt]);
| ^
glo.cpp:135:23: error: no match for 'operator[]' (operand types are 'std::unordered_set<int>' and 'int')
135 | ans=max(ans,solve(w[d]));
| ^
