#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
const int N = 2e5 + 5, INF = 2e9;
vector<int> vs, w[N];
int a[N], t[N * 4], b[N], z[N];
void upd(int x, int y, int v = 1, int L = 0, int R = vs.size() - 1) {
if (L == R) {
t[v] = y;
}
else {
int m = (L + R) >> 1;
if (x <= m)
upd(x, y, v * 2, L, m);
else
upd(x, y, v * 2 + 1, m + 1, R);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
}
int que(int x, int v = 1, int L = 0, int R = vs.size() - 1) {
if (R < x)
return 0;
if (L >= x)
return t[v];
int m = (L + R) >> 1;
return max(que(x, v * 2, L, m),
que(x, v * 2 + 1, m + 1, R));
}
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, x;
cin >> n >> x;
for (int i = 0; i < n; i++) {
cin >> a[i];
vs.push_back(a[i]);
}
sort(all(vs));
vs.erase(unique(all(vs)), vs.end());
for (int i = n - 1; i >= 0; i--) {
b[i] = lower_bound(all(vs), a[i]) - vs.begin();
int lis = que(b[i] + 1) + 1;
w[b[i]].push_back(lis);
upd(b[i], lis);
}
fill(z, z + N, INF);
z[0] = 0;
int ans = 1;
for (int i = 0; i < n; i++) {
w[b[i]].pop_back();
upd(b[i], w[b[i]].empty() ? 0 : w[b[i]].back());
int j = lower_bound(z, z + N, a[i]) - z;
z[j] = a[i];
int k = upper_bound(all(vs), a[i] - x) - vs.begin();
ans = max(ans, que(k) + j);
}
cout << ans << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5756 KB |
Output is correct |
2 |
Correct |
7 ms |
5880 KB |
Output is correct |
3 |
Correct |
7 ms |
5884 KB |
Output is correct |
4 |
Correct |
7 ms |
5752 KB |
Output is correct |
5 |
Correct |
7 ms |
5752 KB |
Output is correct |
6 |
Correct |
7 ms |
5752 KB |
Output is correct |
7 |
Correct |
7 ms |
5756 KB |
Output is correct |
8 |
Correct |
7 ms |
5752 KB |
Output is correct |
9 |
Correct |
7 ms |
5800 KB |
Output is correct |
10 |
Correct |
7 ms |
5852 KB |
Output is correct |
11 |
Correct |
7 ms |
5880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5756 KB |
Output is correct |
2 |
Correct |
7 ms |
5880 KB |
Output is correct |
3 |
Correct |
7 ms |
5884 KB |
Output is correct |
4 |
Correct |
7 ms |
5752 KB |
Output is correct |
5 |
Correct |
7 ms |
5752 KB |
Output is correct |
6 |
Correct |
7 ms |
5752 KB |
Output is correct |
7 |
Correct |
7 ms |
5756 KB |
Output is correct |
8 |
Correct |
7 ms |
5752 KB |
Output is correct |
9 |
Correct |
7 ms |
5800 KB |
Output is correct |
10 |
Correct |
7 ms |
5852 KB |
Output is correct |
11 |
Correct |
7 ms |
5880 KB |
Output is correct |
12 |
Correct |
7 ms |
5880 KB |
Output is correct |
13 |
Correct |
7 ms |
5752 KB |
Output is correct |
14 |
Correct |
9 ms |
5880 KB |
Output is correct |
15 |
Correct |
9 ms |
5752 KB |
Output is correct |
16 |
Correct |
8 ms |
6008 KB |
Output is correct |
17 |
Correct |
7 ms |
5752 KB |
Output is correct |
18 |
Correct |
7 ms |
5880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5756 KB |
Output is correct |
2 |
Correct |
7 ms |
5880 KB |
Output is correct |
3 |
Correct |
7 ms |
5884 KB |
Output is correct |
4 |
Correct |
7 ms |
5752 KB |
Output is correct |
5 |
Correct |
7 ms |
5752 KB |
Output is correct |
6 |
Correct |
7 ms |
5752 KB |
Output is correct |
7 |
Correct |
7 ms |
5756 KB |
Output is correct |
8 |
Correct |
7 ms |
5752 KB |
Output is correct |
9 |
Correct |
7 ms |
5800 KB |
Output is correct |
10 |
Correct |
7 ms |
5852 KB |
Output is correct |
11 |
Correct |
7 ms |
5880 KB |
Output is correct |
12 |
Correct |
7 ms |
5880 KB |
Output is correct |
13 |
Correct |
7 ms |
5752 KB |
Output is correct |
14 |
Correct |
9 ms |
5880 KB |
Output is correct |
15 |
Correct |
9 ms |
5752 KB |
Output is correct |
16 |
Correct |
8 ms |
6008 KB |
Output is correct |
17 |
Correct |
7 ms |
5752 KB |
Output is correct |
18 |
Correct |
7 ms |
5880 KB |
Output is correct |
19 |
Correct |
8 ms |
5880 KB |
Output is correct |
20 |
Correct |
7 ms |
5880 KB |
Output is correct |
21 |
Correct |
8 ms |
5880 KB |
Output is correct |
22 |
Correct |
8 ms |
5880 KB |
Output is correct |
23 |
Correct |
7 ms |
5880 KB |
Output is correct |
24 |
Correct |
7 ms |
5880 KB |
Output is correct |
25 |
Correct |
8 ms |
5880 KB |
Output is correct |
26 |
Correct |
8 ms |
5880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
385 ms |
18408 KB |
Output is correct |
2 |
Correct |
381 ms |
18452 KB |
Output is correct |
3 |
Correct |
414 ms |
18432 KB |
Output is correct |
4 |
Correct |
388 ms |
18520 KB |
Output is correct |
5 |
Correct |
166 ms |
14332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
8948 KB |
Output is correct |
2 |
Correct |
79 ms |
8992 KB |
Output is correct |
3 |
Correct |
78 ms |
8952 KB |
Output is correct |
4 |
Correct |
39 ms |
7928 KB |
Output is correct |
5 |
Correct |
7 ms |
5880 KB |
Output is correct |
6 |
Correct |
45 ms |
7800 KB |
Output is correct |
7 |
Correct |
65 ms |
8952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
136 ms |
12208 KB |
Output is correct |
2 |
Correct |
138 ms |
12224 KB |
Output is correct |
3 |
Correct |
353 ms |
18460 KB |
Output is correct |
4 |
Correct |
138 ms |
14188 KB |
Output is correct |
5 |
Correct |
85 ms |
11764 KB |
Output is correct |
6 |
Correct |
154 ms |
17296 KB |
Output is correct |
7 |
Correct |
152 ms |
17900 KB |
Output is correct |
8 |
Correct |
108 ms |
12140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5756 KB |
Output is correct |
2 |
Correct |
7 ms |
5880 KB |
Output is correct |
3 |
Correct |
7 ms |
5884 KB |
Output is correct |
4 |
Correct |
7 ms |
5752 KB |
Output is correct |
5 |
Correct |
7 ms |
5752 KB |
Output is correct |
6 |
Correct |
7 ms |
5752 KB |
Output is correct |
7 |
Correct |
7 ms |
5756 KB |
Output is correct |
8 |
Correct |
7 ms |
5752 KB |
Output is correct |
9 |
Correct |
7 ms |
5800 KB |
Output is correct |
10 |
Correct |
7 ms |
5852 KB |
Output is correct |
11 |
Correct |
7 ms |
5880 KB |
Output is correct |
12 |
Correct |
7 ms |
5880 KB |
Output is correct |
13 |
Correct |
7 ms |
5752 KB |
Output is correct |
14 |
Correct |
9 ms |
5880 KB |
Output is correct |
15 |
Correct |
9 ms |
5752 KB |
Output is correct |
16 |
Correct |
8 ms |
6008 KB |
Output is correct |
17 |
Correct |
7 ms |
5752 KB |
Output is correct |
18 |
Correct |
7 ms |
5880 KB |
Output is correct |
19 |
Correct |
8 ms |
5880 KB |
Output is correct |
20 |
Correct |
7 ms |
5880 KB |
Output is correct |
21 |
Correct |
8 ms |
5880 KB |
Output is correct |
22 |
Correct |
8 ms |
5880 KB |
Output is correct |
23 |
Correct |
7 ms |
5880 KB |
Output is correct |
24 |
Correct |
7 ms |
5880 KB |
Output is correct |
25 |
Correct |
8 ms |
5880 KB |
Output is correct |
26 |
Correct |
8 ms |
5880 KB |
Output is correct |
27 |
Correct |
385 ms |
18408 KB |
Output is correct |
28 |
Correct |
381 ms |
18452 KB |
Output is correct |
29 |
Correct |
414 ms |
18432 KB |
Output is correct |
30 |
Correct |
388 ms |
18520 KB |
Output is correct |
31 |
Correct |
166 ms |
14332 KB |
Output is correct |
32 |
Correct |
79 ms |
8948 KB |
Output is correct |
33 |
Correct |
79 ms |
8992 KB |
Output is correct |
34 |
Correct |
78 ms |
8952 KB |
Output is correct |
35 |
Correct |
39 ms |
7928 KB |
Output is correct |
36 |
Correct |
7 ms |
5880 KB |
Output is correct |
37 |
Correct |
45 ms |
7800 KB |
Output is correct |
38 |
Correct |
65 ms |
8952 KB |
Output is correct |
39 |
Correct |
136 ms |
12208 KB |
Output is correct |
40 |
Correct |
138 ms |
12224 KB |
Output is correct |
41 |
Correct |
353 ms |
18460 KB |
Output is correct |
42 |
Correct |
138 ms |
14188 KB |
Output is correct |
43 |
Correct |
85 ms |
11764 KB |
Output is correct |
44 |
Correct |
154 ms |
17296 KB |
Output is correct |
45 |
Correct |
152 ms |
17900 KB |
Output is correct |
46 |
Correct |
108 ms |
12140 KB |
Output is correct |
47 |
Correct |
174 ms |
12204 KB |
Output is correct |
48 |
Correct |
166 ms |
12152 KB |
Output is correct |
49 |
Correct |
401 ms |
18340 KB |
Output is correct |
50 |
Correct |
157 ms |
14316 KB |
Output is correct |
51 |
Correct |
130 ms |
12616 KB |
Output is correct |
52 |
Correct |
211 ms |
17716 KB |
Output is correct |
53 |
Correct |
155 ms |
17764 KB |
Output is correct |
54 |
Correct |
161 ms |
18544 KB |
Output is correct |
55 |
Correct |
287 ms |
18552 KB |
Output is correct |