#include <bits/stdc++.h>
#if defined(__GNUC__)
#pragma GCC optimize ("Ofast")
#endif
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
const ld eps=1e-7;
const int inf=2000000010;
const ll INF=10000000000000010LL;
const int mod = 1000000007;
const int MAXN = 200010, LOG=20;
int n, m, k, u, v, x, y, t, a, b, ans;
ll A[MAXN];
ll dp1[MAXN];
ll dp2[MAXN];
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin>>n>>x;
for (int i=1; i<=n; i++) cin>>A[i];
memset(dp1, 31, sizeof(dp1));
memset(dp2, 31, sizeof(dp2));
dp1[0]=dp2[0]=-inf;
for (int i=1; i<=n; i++){
int lis=lower_bound(dp2, dp2+MAXN, A[i])-dp2;
dp2[lis]=min(dp2[lis], A[i]);
ans=max(ans, lis);
lis=lower_bound(dp1, dp1+MAXN, A[i]-x)-dp1;
dp1[lis]=min(dp1[lis], A[i]-x);
dp2[lis]=min(dp2[lis], A[i]-x);
ans=max(ans, lis);
}
cout<<ans<<'\n';
return 0;
}
/*
___ ___ ___ ___ ___ ___ ___ ___
/\ \ /\__\ ___ /\ \ /\__\ /\ \ /\__\ /\ \ /\__\ ___
/::\ \ /:/ / /\ \ /::\ \ /:/ / /::\ \ /:/ / /::\ \ /:/ / /\ \
/:/\:\ \ /:/ / \:\ \ /:/\ \ \ /:/__/ /:/\:\ \ /:/__/ /:/\:\ \ /:/ / \:\ \
/::\~\:\ \ /:/ / /::\__\ _\:\~\ \ \ /::\ \ ___ /::\~\:\ \ /::\ \ ___ /::\~\:\ \ /:/ / /::\__\
/:/\:\ \:\__\ /:/__/ __/:/\/__/ /\ \:\ \ \__\ /:/\:\ /\__\ /:/\:\ \:\__\ /:/\:\ /\__\ /:/\:\ \:\__\ /:/__/ __/:/\/__/
\/__\:\/:/ / \:\ \ /\/:/ / \:\ \:\ \/__/ \/__\:\/:/ / \/__\:\/:/ / \/__\:\/:/ / \/__\:\/:/ / \:\ \ /\/:/ /
\::/ / \:\ \ \::/__/ \:\ \:\__\ \::/ / \::/ / \::/ / \::/ / \:\ \ \::/__/
/:/ / \:\ \ \:\__\ \:\/:/ / /:/ / /:/ / /:/ / /:/ / \:\ \ \:\__\
/:/ / \:\__\ \/__/ \::/ / /:/ / /:/ / /:/ / /:/ / \:\__\ \/__/
\/__/ \/__/ \/__/ \/__/ \/__/ \/__/ \/__/ \/__/
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
3448 KB |
Output is correct |
2 |
Correct |
5 ms |
3448 KB |
Output is correct |
3 |
Correct |
4 ms |
3448 KB |
Output is correct |
4 |
Correct |
5 ms |
3448 KB |
Output is correct |
5 |
Correct |
5 ms |
3448 KB |
Output is correct |
6 |
Correct |
5 ms |
3448 KB |
Output is correct |
7 |
Correct |
4 ms |
3448 KB |
Output is correct |
8 |
Correct |
5 ms |
3448 KB |
Output is correct |
9 |
Correct |
4 ms |
3452 KB |
Output is correct |
10 |
Correct |
5 ms |
3448 KB |
Output is correct |
11 |
Correct |
4 ms |
3448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
3448 KB |
Output is correct |
2 |
Correct |
5 ms |
3448 KB |
Output is correct |
3 |
Correct |
4 ms |
3448 KB |
Output is correct |
4 |
Correct |
5 ms |
3448 KB |
Output is correct |
5 |
Correct |
5 ms |
3448 KB |
Output is correct |
6 |
Correct |
5 ms |
3448 KB |
Output is correct |
7 |
Correct |
4 ms |
3448 KB |
Output is correct |
8 |
Correct |
5 ms |
3448 KB |
Output is correct |
9 |
Correct |
4 ms |
3452 KB |
Output is correct |
10 |
Correct |
5 ms |
3448 KB |
Output is correct |
11 |
Correct |
4 ms |
3448 KB |
Output is correct |
12 |
Correct |
5 ms |
3448 KB |
Output is correct |
13 |
Correct |
4 ms |
3448 KB |
Output is correct |
14 |
Correct |
4 ms |
3448 KB |
Output is correct |
15 |
Correct |
4 ms |
3448 KB |
Output is correct |
16 |
Correct |
5 ms |
3448 KB |
Output is correct |
17 |
Correct |
5 ms |
3448 KB |
Output is correct |
18 |
Correct |
5 ms |
3448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
3448 KB |
Output is correct |
2 |
Correct |
5 ms |
3448 KB |
Output is correct |
3 |
Correct |
4 ms |
3448 KB |
Output is correct |
4 |
Correct |
5 ms |
3448 KB |
Output is correct |
5 |
Correct |
5 ms |
3448 KB |
Output is correct |
6 |
Correct |
5 ms |
3448 KB |
Output is correct |
7 |
Correct |
4 ms |
3448 KB |
Output is correct |
8 |
Correct |
5 ms |
3448 KB |
Output is correct |
9 |
Correct |
4 ms |
3452 KB |
Output is correct |
10 |
Correct |
5 ms |
3448 KB |
Output is correct |
11 |
Correct |
4 ms |
3448 KB |
Output is correct |
12 |
Correct |
5 ms |
3448 KB |
Output is correct |
13 |
Correct |
4 ms |
3448 KB |
Output is correct |
14 |
Correct |
4 ms |
3448 KB |
Output is correct |
15 |
Correct |
4 ms |
3448 KB |
Output is correct |
16 |
Correct |
5 ms |
3448 KB |
Output is correct |
17 |
Correct |
5 ms |
3448 KB |
Output is correct |
18 |
Correct |
5 ms |
3448 KB |
Output is correct |
19 |
Correct |
5 ms |
3448 KB |
Output is correct |
20 |
Correct |
5 ms |
3448 KB |
Output is correct |
21 |
Correct |
5 ms |
3576 KB |
Output is correct |
22 |
Correct |
5 ms |
3448 KB |
Output is correct |
23 |
Correct |
5 ms |
3448 KB |
Output is correct |
24 |
Correct |
5 ms |
3576 KB |
Output is correct |
25 |
Correct |
5 ms |
3448 KB |
Output is correct |
26 |
Correct |
5 ms |
3448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
61 ms |
7036 KB |
Output is correct |
2 |
Correct |
61 ms |
6904 KB |
Output is correct |
3 |
Correct |
62 ms |
6976 KB |
Output is correct |
4 |
Correct |
62 ms |
6904 KB |
Output is correct |
5 |
Correct |
44 ms |
6136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
4344 KB |
Output is correct |
2 |
Correct |
18 ms |
4348 KB |
Output is correct |
3 |
Correct |
18 ms |
4348 KB |
Output is correct |
4 |
Correct |
15 ms |
4220 KB |
Output is correct |
5 |
Correct |
5 ms |
3448 KB |
Output is correct |
6 |
Correct |
15 ms |
4216 KB |
Output is correct |
7 |
Correct |
16 ms |
4408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
5368 KB |
Output is correct |
2 |
Correct |
32 ms |
5240 KB |
Output is correct |
3 |
Correct |
62 ms |
6904 KB |
Output is correct |
4 |
Correct |
49 ms |
6264 KB |
Output is correct |
5 |
Correct |
26 ms |
4856 KB |
Output is correct |
6 |
Correct |
45 ms |
6136 KB |
Output is correct |
7 |
Correct |
48 ms |
6776 KB |
Output is correct |
8 |
Correct |
29 ms |
5284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
3448 KB |
Output is correct |
2 |
Correct |
5 ms |
3448 KB |
Output is correct |
3 |
Correct |
4 ms |
3448 KB |
Output is correct |
4 |
Correct |
5 ms |
3448 KB |
Output is correct |
5 |
Correct |
5 ms |
3448 KB |
Output is correct |
6 |
Correct |
5 ms |
3448 KB |
Output is correct |
7 |
Correct |
4 ms |
3448 KB |
Output is correct |
8 |
Correct |
5 ms |
3448 KB |
Output is correct |
9 |
Correct |
4 ms |
3452 KB |
Output is correct |
10 |
Correct |
5 ms |
3448 KB |
Output is correct |
11 |
Correct |
4 ms |
3448 KB |
Output is correct |
12 |
Correct |
5 ms |
3448 KB |
Output is correct |
13 |
Correct |
4 ms |
3448 KB |
Output is correct |
14 |
Correct |
4 ms |
3448 KB |
Output is correct |
15 |
Correct |
4 ms |
3448 KB |
Output is correct |
16 |
Correct |
5 ms |
3448 KB |
Output is correct |
17 |
Correct |
5 ms |
3448 KB |
Output is correct |
18 |
Correct |
5 ms |
3448 KB |
Output is correct |
19 |
Correct |
5 ms |
3448 KB |
Output is correct |
20 |
Correct |
5 ms |
3448 KB |
Output is correct |
21 |
Correct |
5 ms |
3576 KB |
Output is correct |
22 |
Correct |
5 ms |
3448 KB |
Output is correct |
23 |
Correct |
5 ms |
3448 KB |
Output is correct |
24 |
Correct |
5 ms |
3576 KB |
Output is correct |
25 |
Correct |
5 ms |
3448 KB |
Output is correct |
26 |
Correct |
5 ms |
3448 KB |
Output is correct |
27 |
Correct |
61 ms |
7036 KB |
Output is correct |
28 |
Correct |
61 ms |
6904 KB |
Output is correct |
29 |
Correct |
62 ms |
6976 KB |
Output is correct |
30 |
Correct |
62 ms |
6904 KB |
Output is correct |
31 |
Correct |
44 ms |
6136 KB |
Output is correct |
32 |
Correct |
18 ms |
4344 KB |
Output is correct |
33 |
Correct |
18 ms |
4348 KB |
Output is correct |
34 |
Correct |
18 ms |
4348 KB |
Output is correct |
35 |
Correct |
15 ms |
4220 KB |
Output is correct |
36 |
Correct |
5 ms |
3448 KB |
Output is correct |
37 |
Correct |
15 ms |
4216 KB |
Output is correct |
38 |
Correct |
16 ms |
4408 KB |
Output is correct |
39 |
Correct |
32 ms |
5368 KB |
Output is correct |
40 |
Correct |
32 ms |
5240 KB |
Output is correct |
41 |
Correct |
62 ms |
6904 KB |
Output is correct |
42 |
Correct |
49 ms |
6264 KB |
Output is correct |
43 |
Correct |
26 ms |
4856 KB |
Output is correct |
44 |
Correct |
45 ms |
6136 KB |
Output is correct |
45 |
Correct |
48 ms |
6776 KB |
Output is correct |
46 |
Correct |
29 ms |
5284 KB |
Output is correct |
47 |
Correct |
32 ms |
5268 KB |
Output is correct |
48 |
Correct |
32 ms |
5240 KB |
Output is correct |
49 |
Correct |
64 ms |
7004 KB |
Output is correct |
50 |
Correct |
44 ms |
6208 KB |
Output is correct |
51 |
Correct |
42 ms |
5496 KB |
Output is correct |
52 |
Correct |
49 ms |
6228 KB |
Output is correct |
53 |
Correct |
44 ms |
6344 KB |
Output is correct |
54 |
Correct |
51 ms |
7028 KB |
Output is correct |
55 |
Correct |
54 ms |
7048 KB |
Output is correct |