#include <bits/stdc++.h>
using namespace std;
const int N = 200'000 + 10;
int n, x;
int a[N];
vector<int> rrh;
int f[N << 2];
void update(int s, int l, int r, int i, int value) {
if (i < l || i > r) return;
if (l == r) {
f[s] = value;
return;
}
int mid = l + r >> 1;
update(s << 1, l, mid, i, value); update(s << 1 | 1, mid + 1, r, i, value);
f[s] = max(f[s << 1], f[s << 1 | 1]);
}
int query(int s, int l, int r, int u, int v) {
if (v < l || u > r) return 0;
if (u <= l && r <= v) return f[s];
int mid = l + r >> 1;
return max(query(s << 1, l, mid, u, v), query(s << 1 | 1, mid + 1, r, u, v));
}
int fwd[N], bwd[N];
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> x;
for (int i = 1; i <= n; ++i) cin >> a[i];
rrh = vector<int> (a + 1, a + n + 1);
sort(rrh.begin(), rrh.end());
rrh.resize(unique(rrh.begin(), rrh.end()) - rrh.begin());
for (int i = 1; i <= n; ++i) {
int r = lower_bound(rrh.begin(), rrh.end(), a[i]) - rrh.begin() + 1;
fwd[i] = query(1, 1, rrh.size(), 1, r - 1) + 1;
update(1, 1, rrh.size(), r, fwd[i]);
}
memset(f, 0, sizeof f);
for (int i = n; i >= 1; --i) {
int l = lower_bound(rrh.begin(), rrh.end(), a[i]) - rrh.begin() + 1;
bwd[i] = query(1, 1, rrh.size(), l + 1, rrh.size()) + 1;
update(1, 1, rrh.size(), l, bwd[i]);
}
memset(f, 0, sizeof f);
int answer = 0;
for (int i = 1; i <= n; ++i) {
int it = upper_bound(rrh.begin(), rrh.end(), x - a[i]) - rrh.begin();
answer = max(answer, bwd[i] + query(1, 1, rrh.size(), 1, it));
int r = lower_bound(rrh.begin(), rrh.end(), a[i]) - rrh.begin() + 1;
update(1, 1, rrh.size(), r, fwd[i]);
}
memset(f, 0, sizeof f);
for (int i = n; i >= 1; --i) {
int it = upper_bound(rrh.begin(), rrh.end(), a[i] - x) - rrh.begin() + 1;
answer = max(answer, fwd[i] + query(1, 1, rrh.size(), it, rrh.size()));
int l = lower_bound(rrh.begin(), rrh.end(), a[i]) - rrh.begin() + 1;
update(1, 1, rrh.size(), l, bwd[i]);
}
cout << answer << "\n";
}
Compilation message
glo.cpp: In function 'void update(int, int, int, int, int)':
glo.cpp:18:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
18 | int mid = l + r >> 1;
| ~~^~~
glo.cpp: In function 'int query(int, int, int, int, int)':
glo.cpp:25:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
25 | int mid = l + r >> 1;
| ~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4952 KB |
Output is correct |
2 |
Correct |
2 ms |
4956 KB |
Output is correct |
3 |
Correct |
1 ms |
4952 KB |
Output is correct |
4 |
Correct |
1 ms |
4956 KB |
Output is correct |
5 |
Correct |
1 ms |
4952 KB |
Output is correct |
6 |
Correct |
1 ms |
4956 KB |
Output is correct |
7 |
Correct |
1 ms |
4956 KB |
Output is correct |
8 |
Correct |
1 ms |
3420 KB |
Output is correct |
9 |
Correct |
1 ms |
4956 KB |
Output is correct |
10 |
Correct |
1 ms |
4956 KB |
Output is correct |
11 |
Correct |
1 ms |
4956 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4952 KB |
Output is correct |
2 |
Correct |
2 ms |
4956 KB |
Output is correct |
3 |
Correct |
1 ms |
4952 KB |
Output is correct |
4 |
Correct |
1 ms |
4956 KB |
Output is correct |
5 |
Correct |
1 ms |
4952 KB |
Output is correct |
6 |
Correct |
1 ms |
4956 KB |
Output is correct |
7 |
Correct |
1 ms |
4956 KB |
Output is correct |
8 |
Correct |
1 ms |
3420 KB |
Output is correct |
9 |
Correct |
1 ms |
4956 KB |
Output is correct |
10 |
Correct |
1 ms |
4956 KB |
Output is correct |
11 |
Correct |
1 ms |
4956 KB |
Output is correct |
12 |
Correct |
1 ms |
3420 KB |
Output is correct |
13 |
Correct |
1 ms |
3420 KB |
Output is correct |
14 |
Correct |
1 ms |
3420 KB |
Output is correct |
15 |
Correct |
1 ms |
4952 KB |
Output is correct |
16 |
Correct |
1 ms |
3420 KB |
Output is correct |
17 |
Correct |
1 ms |
4956 KB |
Output is correct |
18 |
Correct |
1 ms |
3420 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4952 KB |
Output is correct |
2 |
Correct |
2 ms |
4956 KB |
Output is correct |
3 |
Correct |
1 ms |
4952 KB |
Output is correct |
4 |
Correct |
1 ms |
4956 KB |
Output is correct |
5 |
Correct |
1 ms |
4952 KB |
Output is correct |
6 |
Correct |
1 ms |
4956 KB |
Output is correct |
7 |
Correct |
1 ms |
4956 KB |
Output is correct |
8 |
Correct |
1 ms |
3420 KB |
Output is correct |
9 |
Correct |
1 ms |
4956 KB |
Output is correct |
10 |
Correct |
1 ms |
4956 KB |
Output is correct |
11 |
Correct |
1 ms |
4956 KB |
Output is correct |
12 |
Correct |
1 ms |
3420 KB |
Output is correct |
13 |
Correct |
1 ms |
3420 KB |
Output is correct |
14 |
Correct |
1 ms |
3420 KB |
Output is correct |
15 |
Correct |
1 ms |
4952 KB |
Output is correct |
16 |
Correct |
1 ms |
3420 KB |
Output is correct |
17 |
Correct |
1 ms |
4956 KB |
Output is correct |
18 |
Correct |
1 ms |
3420 KB |
Output is correct |
19 |
Correct |
2 ms |
3420 KB |
Output is correct |
20 |
Correct |
2 ms |
3420 KB |
Output is correct |
21 |
Correct |
2 ms |
3420 KB |
Output is correct |
22 |
Correct |
2 ms |
3420 KB |
Output is correct |
23 |
Correct |
2 ms |
3420 KB |
Output is correct |
24 |
Correct |
2 ms |
3416 KB |
Output is correct |
25 |
Correct |
2 ms |
4956 KB |
Output is correct |
26 |
Correct |
2 ms |
3420 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
386 ms |
6584 KB |
Output is correct |
2 |
Correct |
386 ms |
6656 KB |
Output is correct |
3 |
Correct |
369 ms |
6656 KB |
Output is correct |
4 |
Correct |
381 ms |
6644 KB |
Output is correct |
5 |
Correct |
184 ms |
6608 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
89 ms |
4356 KB |
Output is correct |
2 |
Correct |
81 ms |
4176 KB |
Output is correct |
3 |
Correct |
83 ms |
4208 KB |
Output is correct |
4 |
Correct |
43 ms |
4184 KB |
Output is correct |
5 |
Correct |
1 ms |
4956 KB |
Output is correct |
6 |
Correct |
47 ms |
4560 KB |
Output is correct |
7 |
Correct |
69 ms |
4692 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
182 ms |
5048 KB |
Output is correct |
2 |
Correct |
175 ms |
4948 KB |
Output is correct |
3 |
Correct |
395 ms |
6484 KB |
Output is correct |
4 |
Correct |
177 ms |
6484 KB |
Output is correct |
5 |
Correct |
107 ms |
5600 KB |
Output is correct |
6 |
Correct |
211 ms |
7540 KB |
Output is correct |
7 |
Correct |
196 ms |
8336 KB |
Output is correct |
8 |
Correct |
140 ms |
5968 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4952 KB |
Output is correct |
2 |
Correct |
2 ms |
4956 KB |
Output is correct |
3 |
Correct |
1 ms |
4952 KB |
Output is correct |
4 |
Correct |
1 ms |
4956 KB |
Output is correct |
5 |
Correct |
1 ms |
4952 KB |
Output is correct |
6 |
Correct |
1 ms |
4956 KB |
Output is correct |
7 |
Correct |
1 ms |
4956 KB |
Output is correct |
8 |
Correct |
1 ms |
3420 KB |
Output is correct |
9 |
Correct |
1 ms |
4956 KB |
Output is correct |
10 |
Correct |
1 ms |
4956 KB |
Output is correct |
11 |
Correct |
1 ms |
4956 KB |
Output is correct |
12 |
Correct |
1 ms |
3420 KB |
Output is correct |
13 |
Correct |
1 ms |
3420 KB |
Output is correct |
14 |
Correct |
1 ms |
3420 KB |
Output is correct |
15 |
Correct |
1 ms |
4952 KB |
Output is correct |
16 |
Correct |
1 ms |
3420 KB |
Output is correct |
17 |
Correct |
1 ms |
4956 KB |
Output is correct |
18 |
Correct |
1 ms |
3420 KB |
Output is correct |
19 |
Correct |
2 ms |
3420 KB |
Output is correct |
20 |
Correct |
2 ms |
3420 KB |
Output is correct |
21 |
Correct |
2 ms |
3420 KB |
Output is correct |
22 |
Correct |
2 ms |
3420 KB |
Output is correct |
23 |
Correct |
2 ms |
3420 KB |
Output is correct |
24 |
Correct |
2 ms |
3416 KB |
Output is correct |
25 |
Correct |
2 ms |
4956 KB |
Output is correct |
26 |
Correct |
2 ms |
3420 KB |
Output is correct |
27 |
Correct |
386 ms |
6584 KB |
Output is correct |
28 |
Correct |
386 ms |
6656 KB |
Output is correct |
29 |
Correct |
369 ms |
6656 KB |
Output is correct |
30 |
Correct |
381 ms |
6644 KB |
Output is correct |
31 |
Correct |
184 ms |
6608 KB |
Output is correct |
32 |
Correct |
89 ms |
4356 KB |
Output is correct |
33 |
Correct |
81 ms |
4176 KB |
Output is correct |
34 |
Correct |
83 ms |
4208 KB |
Output is correct |
35 |
Correct |
43 ms |
4184 KB |
Output is correct |
36 |
Correct |
1 ms |
4956 KB |
Output is correct |
37 |
Correct |
47 ms |
4560 KB |
Output is correct |
38 |
Correct |
69 ms |
4692 KB |
Output is correct |
39 |
Correct |
182 ms |
5048 KB |
Output is correct |
40 |
Correct |
175 ms |
4948 KB |
Output is correct |
41 |
Correct |
395 ms |
6484 KB |
Output is correct |
42 |
Correct |
177 ms |
6484 KB |
Output is correct |
43 |
Correct |
107 ms |
5600 KB |
Output is correct |
44 |
Correct |
211 ms |
7540 KB |
Output is correct |
45 |
Correct |
196 ms |
8336 KB |
Output is correct |
46 |
Correct |
140 ms |
5968 KB |
Output is correct |
47 |
Correct |
172 ms |
5972 KB |
Output is correct |
48 |
Correct |
173 ms |
5972 KB |
Output is correct |
49 |
Correct |
374 ms |
8572 KB |
Output is correct |
50 |
Correct |
201 ms |
7844 KB |
Output is correct |
51 |
Correct |
173 ms |
7120 KB |
Output is correct |
52 |
Correct |
291 ms |
7992 KB |
Output is correct |
53 |
Correct |
203 ms |
7764 KB |
Output is correct |
54 |
Correct |
206 ms |
8636 KB |
Output is correct |
55 |
Correct |
311 ms |
8660 KB |
Output is correct |