#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MIN = -2000000001;
const int MAX = 2000000001;
int n, x;
const int N = 200005;
int tree[4 * N][2];
int getMax(int from, int to, int a, int b, int node, int treeNum) {
if (from > to) return 0;
if (from <= a && b <= to) return tree[node][treeNum];
int mid = (a + b) / 2;
int res = -1;
if (from <= mid) res = max(res, getMax(from, to, a, mid, node * 2, treeNum));
if (to > mid) res = max(res, getMax(from, to, mid +1, b, node * 2 + 1, treeNum));
return res;
}
void insertMax(int i, int num, int a, int b, int node, int treeNum) {
if (a == b) {
tree[node][treeNum] = max(tree[node][treeNum], num);
return;
}
int mid = (a + b) / 2;
if (i <= mid) insertMax(i, num, a, mid, node * 2, treeNum);
else insertMax(i, num, mid + 1, b, node * 2 + 1, treeNum);
tree[node][treeNum] = max(tree[node * 2][treeNum], tree[node * 2 + 1][treeNum]);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> x;
vector<int> v(n);
for (int i = 0; i < n; i++) cin >> v[i];
if (n == 1) {
cout << 1 << "\n";
return 0;
}
vector<int> left(n);
set<int> all;
map<int, int> mapTo;
for (int i = 0; i < n; i++) all.insert(v[i]);
int cur = 0;
for (int i : all) {
mapTo[i] = cur;
cur++;
}
vector<int> getsTo(n);
vector<int> org(v.begin(), v.end());
set<array<int, 2>> orgAndNew;
for (int i = 0; i < n; i++) {
v[i] = mapTo[v[i]];
orgAndNew.insert({org[i], v[i]});
}
for (int i = 0; i < n; i++) {
auto it = orgAndNew.upper_bound({org[i] + x, -1});
if (it == orgAndNew.begin()) {
getsTo[v[i]] = -1;
} else {
it--;
getsTo[v[i]] = (*it)[1];
}
}
for (int i = 0; i < n; i++) {
insertMax(v[i], 1 + getMax(0, getsTo[v[i]], 0, N - 1, 1, 0), 0, N - 1, 1, 1);
insertMax(v[i], 1 + getMax(0, v[i] - 1, 0, N - 1, 1, 0), 0, N - 1, 1, 0);
insertMax(v[i], 1 + getMax(0, v[i] - 1, 0, N - 1, 1, 1), 0, N - 1, 1, 1);
}
cout << getMax(0, N - 1, 0, N - 1, 1, 1) << "\n";
}
/*
8 10
7 3 5 12 2 7 3 4
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
0 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
0 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
3 ms |
460 KB |
Output is correct |
20 |
Correct |
3 ms |
460 KB |
Output is correct |
21 |
Correct |
2 ms |
460 KB |
Output is correct |
22 |
Correct |
2 ms |
460 KB |
Output is correct |
23 |
Correct |
2 ms |
460 KB |
Output is correct |
24 |
Correct |
2 ms |
460 KB |
Output is correct |
25 |
Correct |
2 ms |
460 KB |
Output is correct |
26 |
Correct |
2 ms |
460 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
797 ms |
35732 KB |
Output is correct |
2 |
Correct |
869 ms |
35772 KB |
Output is correct |
3 |
Correct |
813 ms |
35788 KB |
Output is correct |
4 |
Correct |
832 ms |
35812 KB |
Output is correct |
5 |
Correct |
339 ms |
19612 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
137 ms |
9188 KB |
Output is correct |
2 |
Correct |
137 ms |
9156 KB |
Output is correct |
3 |
Correct |
144 ms |
9112 KB |
Output is correct |
4 |
Correct |
75 ms |
5140 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
83 ms |
5164 KB |
Output is correct |
7 |
Correct |
132 ms |
9172 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
293 ms |
18068 KB |
Output is correct |
2 |
Correct |
297 ms |
17988 KB |
Output is correct |
3 |
Correct |
694 ms |
35800 KB |
Output is correct |
4 |
Correct |
335 ms |
19660 KB |
Output is correct |
5 |
Correct |
212 ms |
17972 KB |
Output is correct |
6 |
Correct |
393 ms |
34024 KB |
Output is correct |
7 |
Correct |
388 ms |
34200 KB |
Output is correct |
8 |
Correct |
255 ms |
17976 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
0 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
3 ms |
460 KB |
Output is correct |
20 |
Correct |
3 ms |
460 KB |
Output is correct |
21 |
Correct |
2 ms |
460 KB |
Output is correct |
22 |
Correct |
2 ms |
460 KB |
Output is correct |
23 |
Correct |
2 ms |
460 KB |
Output is correct |
24 |
Correct |
2 ms |
460 KB |
Output is correct |
25 |
Correct |
2 ms |
460 KB |
Output is correct |
26 |
Correct |
2 ms |
460 KB |
Output is correct |
27 |
Correct |
797 ms |
35732 KB |
Output is correct |
28 |
Correct |
869 ms |
35772 KB |
Output is correct |
29 |
Correct |
813 ms |
35788 KB |
Output is correct |
30 |
Correct |
832 ms |
35812 KB |
Output is correct |
31 |
Correct |
339 ms |
19612 KB |
Output is correct |
32 |
Correct |
137 ms |
9188 KB |
Output is correct |
33 |
Correct |
137 ms |
9156 KB |
Output is correct |
34 |
Correct |
144 ms |
9112 KB |
Output is correct |
35 |
Correct |
75 ms |
5140 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
83 ms |
5164 KB |
Output is correct |
38 |
Correct |
132 ms |
9172 KB |
Output is correct |
39 |
Correct |
293 ms |
18068 KB |
Output is correct |
40 |
Correct |
297 ms |
17988 KB |
Output is correct |
41 |
Correct |
694 ms |
35800 KB |
Output is correct |
42 |
Correct |
335 ms |
19660 KB |
Output is correct |
43 |
Correct |
212 ms |
17972 KB |
Output is correct |
44 |
Correct |
393 ms |
34024 KB |
Output is correct |
45 |
Correct |
388 ms |
34200 KB |
Output is correct |
46 |
Correct |
255 ms |
17976 KB |
Output is correct |
47 |
Correct |
316 ms |
19048 KB |
Output is correct |
48 |
Correct |
326 ms |
18928 KB |
Output is correct |
49 |
Correct |
779 ms |
37660 KB |
Output is correct |
50 |
Correct |
339 ms |
20756 KB |
Output is correct |
51 |
Correct |
285 ms |
19692 KB |
Output is correct |
52 |
Correct |
432 ms |
37056 KB |
Output is correct |
53 |
Correct |
427 ms |
36940 KB |
Output is correct |
54 |
Correct |
425 ms |
37680 KB |
Output is correct |
55 |
Correct |
615 ms |
37684 KB |
Output is correct |