#include <bits/stdc++.h>
using namespace std;
const int N=(int) 2e5+9;
unordered_map <long long , long long > nen;
long long a[N],f[N],temp[N],f2[N];
long long st[4*N];
long long res,dp;
int n,x,idx,t;
void up(int id, int l, int r, int vt, int val) {
if (l>vt || r<vt) return;
if (l==r ) {
st[id]=val;
return;
}
// if (vt==2)
// cout<<l<<" "<<r<<endl;
int m=(l+r)/2;
up(id*2,l,m,vt,val);
up(id*2+1,m+1,r,vt,val);
st[id]=max(st[id*2],st[id*2+1]);
}
long long get(int id, int l, int r, int u, int v) {
if (l>v || r <u) return (int) -1e12;
if (u<=l && r<=v) return st[id];
int m=(l+r)/2;
long long get1=get(id*2,l,m,u,v);
long long get2=get(id*2+1,m+1,r,u,v);
// if (u==2) {
// cout<<l<<" "<<r<<endl;
// cout<<get1<<" "<<get2<<endl;
// cout<<endl;
// }
return max(get1,get2);
}
int small(int l, int r,long long x) {
int vt=r;
while (l<=r) {
int m=(l+r)/2;
if (temp[m]<=x) vt=m,r=m-1;
else l=m+1;
}
return vt;
}
void solve() {
res=idx;
int pos=nen[a[n]];
up(1,1,t,pos,f2[n]);
for (int i=n-1; i>=1; i--) {
int vt=upper_bound(temp+1,temp+1+n,a[i]-x)-temp;
int pos=nen[temp[vt]];
dp=get(1,1,t,pos,t);
res=max(res,dp+f[i]);
pos=nen[a[i]];
up(1,1,t,pos,f2[i]);
}
cout<<res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// freopen("daydep.inp","r",stdin);
//freopen("daydep.out","w",stdout);
cin>>n>>x;
for (int i=1; i<=n; i++)
cin>>a[i];
for (int i=1; i<=n; i++) {
temp[idx+1]=100000000;
int pos=lower_bound(temp+1,temp+idx+1,a[i])-temp;
temp[pos]=a[i];
idx=max(idx,pos);
f[i]=pos;
}
for (int i=1; i<=n; i++) temp[i]=0;
idx=0;
for (int i=n; i>=1; i--) {
temp[idx+1]=-1000000000;
int pos=small(1,idx+1,a[i]);
temp[pos]=a[i];
idx=max(idx,pos);
f2[i]=pos;
}
for (int i=1; i<=n; i++)
temp[i]=a[i];
sort(temp+1,temp+1+n);
for (int i=1; i<=n; i++) {
if (temp[i]!=temp[i-1]) t++;
nen[temp[i]]=t;
}
solve();
return 0;
}
Compilation message
glo.cpp:96:2: error: extended character is not valid in an identifier
96 | temp[idx+1]=100000000;
| ^
glo.cpp:96:5: error: extended character is not valid in an identifier
96 | temp[idx+1]=100000000;
| ^
glo.cpp:96:8: error: extended character is not valid in an identifier
96 | temp[idx+1]=100000000;
| ^
glo.cpp:96:11: error: extended character is not valid in an identifier
96 | temp[idx+1]=100000000;
| ^
glo.cpp:107:2: error: extended character is not valid in an identifier
107 | temp[idx+1]=-1000000000;
| ^
glo.cpp:107:5: error: extended character is not valid in an identifier
107 | temp[idx+1]=-1000000000;
| ^
glo.cpp:107:8: error: extended character is not valid in an identifier
107 | temp[idx+1]=-1000000000;
| ^
glo.cpp:107:11: error: extended character is not valid in an identifier
107 | temp[idx+1]=-1000000000;
| ^
glo.cpp: In function 'int main()':
glo.cpp:96:2: error: '\U000000a0' was not declared in this scope
96 | temp[idx+1]=100000000;
| ^
glo.cpp:107:2: error: '\U000000a0' was not declared in this scope
107 | temp[idx+1]=-1000000000;
| ^
