#include <bits/stdc++.h>
#define ll long long
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz size()
#define vll vector<ll>
#define bc back()
#define arr array
#define pll vector<pair<ll,ll>>
using namespace std;/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>*/
template<class S,class T>
bool chmin(S &a,const T &b) {
return a>b?(a=b)==b:false;
}
template<class S,class T>
bool chmax(S &a,const T &b) {
return a<b?(a=b)==b:false;
}
//void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
const ll inf=1e18;
const ll mod=998244353;
const ll N=1e6+5;
const ld eps=1e-9;
vll t0(N*4),t1(N*4);
void upd(ll id,ll pos,ll val,ll v=1,ll tl=1,ll tr=N){
if(tl>pos || tr<pos) return;
if(tl==tr){
if(!id) chmax(t0[v],val);
chmax(t1[v],val);
return;
}
ll tm=(tl+tr)/2;
upd(id,pos,val,v*2,tl,tm);
upd(id,pos,val,v*2+1,tm+1,tr);
t0[v]=max(t0[v*2],t0[v*2+1]);
t1[v]=max(t1[v*2],t1[v*2+1]);
}
ll get(ll id,ll l,ll r,ll v=1,ll tl=1,ll tr=N){
if(tl>r || tr<l) return 0;
if(l<=tl && tr<=r)return (id ? t1[v] : max(t1[v],t0[v]));
ll tm=(tl+tr)/2;
return max(get(id,l,r,v*2,tl,tm),get(id,l,r,v*2+1,tm+1,tr));
}
void solve(){
ll i,j;
ll n,x;
cin>>n>>x;
ll a[n+5];
set<ll> st;
for(i=1;i<=n;i++){
cin>>a[i];
st.ins(a[i]);
st.ins(a[i]+x);
}
map<ll,ll> pos;
ll c=1;
for(auto i : st){
pos[i]=c++;
}
for(i=1;i<=n;i++){
ll y2=get(1,1,pos[a[i]+x]-1);
upd(1,pos[a[i]+x],y2+1);
ll y=get(0,1,pos[a[i]]-1);
upd(0,pos[a[i]],y+1);
}
cout<<get(1,1,st.sz+1)<<endl;
}
signed main(){
start();
ll t=1;
//cin>>t;
while(t--) solve();
return 0;
}
/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/
Compilation message
glo.cpp: In function 'void solve()':
glo.cpp:66:10: warning: unused variable 'j' [-Wunused-variable]
66 | ll i,j;
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
63068 KB |
Output is correct |
2 |
Correct |
9 ms |
63068 KB |
Output is correct |
3 |
Correct |
10 ms |
63068 KB |
Output is correct |
4 |
Correct |
10 ms |
62932 KB |
Output is correct |
5 |
Correct |
9 ms |
63068 KB |
Output is correct |
6 |
Correct |
9 ms |
63068 KB |
Output is correct |
7 |
Correct |
9 ms |
62996 KB |
Output is correct |
8 |
Correct |
9 ms |
63064 KB |
Output is correct |
9 |
Correct |
10 ms |
63064 KB |
Output is correct |
10 |
Incorrect |
10 ms |
63064 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
63068 KB |
Output is correct |
2 |
Correct |
9 ms |
63068 KB |
Output is correct |
3 |
Correct |
10 ms |
63068 KB |
Output is correct |
4 |
Correct |
10 ms |
62932 KB |
Output is correct |
5 |
Correct |
9 ms |
63068 KB |
Output is correct |
6 |
Correct |
9 ms |
63068 KB |
Output is correct |
7 |
Correct |
9 ms |
62996 KB |
Output is correct |
8 |
Correct |
9 ms |
63064 KB |
Output is correct |
9 |
Correct |
10 ms |
63064 KB |
Output is correct |
10 |
Incorrect |
10 ms |
63064 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
63068 KB |
Output is correct |
2 |
Correct |
9 ms |
63068 KB |
Output is correct |
3 |
Correct |
10 ms |
63068 KB |
Output is correct |
4 |
Correct |
10 ms |
62932 KB |
Output is correct |
5 |
Correct |
9 ms |
63068 KB |
Output is correct |
6 |
Correct |
9 ms |
63068 KB |
Output is correct |
7 |
Correct |
9 ms |
62996 KB |
Output is correct |
8 |
Correct |
9 ms |
63064 KB |
Output is correct |
9 |
Correct |
10 ms |
63064 KB |
Output is correct |
10 |
Incorrect |
10 ms |
63064 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
466 ms |
86548 KB |
Output is correct |
2 |
Correct |
483 ms |
86608 KB |
Output is correct |
3 |
Correct |
448 ms |
86356 KB |
Output is correct |
4 |
Correct |
504 ms |
86552 KB |
Output is correct |
5 |
Correct |
245 ms |
75560 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
114 ms |
74224 KB |
Output is correct |
2 |
Correct |
112 ms |
74320 KB |
Output is correct |
3 |
Correct |
112 ms |
74412 KB |
Output is correct |
4 |
Incorrect |
73 ms |
68700 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
338 ms |
85844 KB |
Output is correct |
2 |
Correct |
319 ms |
85708 KB |
Output is correct |
3 |
Correct |
905 ms |
108628 KB |
Output is correct |
4 |
Correct |
285 ms |
86608 KB |
Output is correct |
5 |
Correct |
186 ms |
85536 KB |
Output is correct |
6 |
Correct |
356 ms |
106068 KB |
Output is correct |
7 |
Correct |
373 ms |
106184 KB |
Output is correct |
8 |
Correct |
223 ms |
85656 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
63068 KB |
Output is correct |
2 |
Correct |
9 ms |
63068 KB |
Output is correct |
3 |
Correct |
10 ms |
63068 KB |
Output is correct |
4 |
Correct |
10 ms |
62932 KB |
Output is correct |
5 |
Correct |
9 ms |
63068 KB |
Output is correct |
6 |
Correct |
9 ms |
63068 KB |
Output is correct |
7 |
Correct |
9 ms |
62996 KB |
Output is correct |
8 |
Correct |
9 ms |
63064 KB |
Output is correct |
9 |
Correct |
10 ms |
63064 KB |
Output is correct |
10 |
Incorrect |
10 ms |
63064 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |