#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define maxn 520000
int n, x, bit1[maxn], bit2[maxn], a[maxn], mxv, nx[maxn];
void att1(int pos, int val) {
for(int i = pos; i <= mxv; i+= i&-i) {
bit1[i] = max(bit1[i],val);
}
}
int qrr1(int pos) {
int val = 0;
for(int i = pos; i > 0; i-= i&-i) {
val = max(val,bit1[i]);
}
return val;
}
void att2(int pos, int val) {
for(int i = pos; i <= mxv; i+= i&-i) {
bit2[i] = max(bit2[i],val);
}
}
int qrr2(int pos) {
int val = 0;
for(int i = pos; i > 0; i-= i&-i) {
val = max(val,bit2[i]);
}
return val;
}
void solve() {
cin >> n >> x;
vector<int> cc;
for(int i = 1; i <= n; i++) {
cin >> a[i];
cc.pb(a[i]);
cc.pb(a[i]+x);
}
sort(all(cc));
cc.erase(unique(all(cc)),cc.end());
mxv = cc.size()+1;
for(int i = 1; i <= n; i++) {
nx[i] = upper_bound(all(cc),a[i]+x) - cc.begin();
a[i] = upper_bound(all(cc),a[i]) - cc.begin();
}
int ans = 0;
for(int i = 1; i <= n; i++) {
// cout << i << " " << a[i] << " " << nx[i] << endl;
// se ja usou
int ans2 = qrr2(a[i]-1) + 1;
ans = max(ans, ans2);
att2(a[i],ans2);
// nao usou
int ans3 = qrr1(nx[i]-1) + 1;
ans = max(ans, ans3);
att2(a[i],ans3);
int ans1 = qrr1(a[i]-1) + 1;
ans = max(ans, ans1);
att1(a[i],ans1);
}
cout << ans << endl;
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(0);
// freopen("in.in", "r", stdin);
//freopen("out.out", "w", stdout);
int tt = 1;
// cin >> tt;
while(tt--) solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
324 KB |
Output is correct |
7 |
Correct |
1 ms |
320 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
324 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
324 KB |
Output is correct |
7 |
Correct |
1 ms |
320 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
324 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
324 KB |
Output is correct |
13 |
Correct |
1 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 |
0 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
308 KB |
Output is correct |
18 |
Correct |
1 ms |
320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
324 KB |
Output is correct |
7 |
Correct |
1 ms |
320 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
324 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
324 KB |
Output is correct |
13 |
Correct |
1 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 |
0 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
308 KB |
Output is correct |
18 |
Correct |
1 ms |
320 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
328 KB |
Output is correct |
21 |
Correct |
1 ms |
328 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
304 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
324 KB |
Output is correct |
26 |
Correct |
1 ms |
324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
123 ms |
9776 KB |
Output is correct |
2 |
Correct |
120 ms |
9752 KB |
Output is correct |
3 |
Correct |
114 ms |
9776 KB |
Output is correct |
4 |
Correct |
118 ms |
9776 KB |
Output is correct |
5 |
Correct |
63 ms |
8240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
3592 KB |
Output is correct |
2 |
Correct |
36 ms |
3520 KB |
Output is correct |
3 |
Correct |
31 ms |
3572 KB |
Output is correct |
4 |
Correct |
15 ms |
2812 KB |
Output is correct |
5 |
Correct |
0 ms |
316 KB |
Output is correct |
6 |
Correct |
16 ms |
3008 KB |
Output is correct |
7 |
Correct |
24 ms |
3764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
5156 KB |
Output is correct |
2 |
Correct |
63 ms |
6076 KB |
Output is correct |
3 |
Correct |
140 ms |
10776 KB |
Output is correct |
4 |
Correct |
68 ms |
9164 KB |
Output is correct |
5 |
Correct |
37 ms |
5748 KB |
Output is correct |
6 |
Correct |
68 ms |
10628 KB |
Output is correct |
7 |
Correct |
84 ms |
10612 KB |
Output is correct |
8 |
Correct |
56 ms |
6148 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
324 KB |
Output is correct |
7 |
Correct |
1 ms |
320 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
324 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
324 KB |
Output is correct |
13 |
Correct |
1 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 |
0 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
308 KB |
Output is correct |
18 |
Correct |
1 ms |
320 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
328 KB |
Output is correct |
21 |
Correct |
1 ms |
328 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
304 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
324 KB |
Output is correct |
26 |
Correct |
1 ms |
324 KB |
Output is correct |
27 |
Correct |
123 ms |
9776 KB |
Output is correct |
28 |
Correct |
120 ms |
9752 KB |
Output is correct |
29 |
Correct |
114 ms |
9776 KB |
Output is correct |
30 |
Correct |
118 ms |
9776 KB |
Output is correct |
31 |
Correct |
63 ms |
8240 KB |
Output is correct |
32 |
Correct |
42 ms |
3592 KB |
Output is correct |
33 |
Correct |
36 ms |
3520 KB |
Output is correct |
34 |
Correct |
31 ms |
3572 KB |
Output is correct |
35 |
Correct |
15 ms |
2812 KB |
Output is correct |
36 |
Correct |
0 ms |
316 KB |
Output is correct |
37 |
Correct |
16 ms |
3008 KB |
Output is correct |
38 |
Correct |
24 ms |
3764 KB |
Output is correct |
39 |
Correct |
62 ms |
5156 KB |
Output is correct |
40 |
Correct |
63 ms |
6076 KB |
Output is correct |
41 |
Correct |
140 ms |
10776 KB |
Output is correct |
42 |
Correct |
68 ms |
9164 KB |
Output is correct |
43 |
Correct |
37 ms |
5748 KB |
Output is correct |
44 |
Correct |
68 ms |
10628 KB |
Output is correct |
45 |
Correct |
84 ms |
10612 KB |
Output is correct |
46 |
Correct |
56 ms |
6148 KB |
Output is correct |
47 |
Correct |
60 ms |
7612 KB |
Output is correct |
48 |
Correct |
59 ms |
7608 KB |
Output is correct |
49 |
Correct |
188 ms |
14208 KB |
Output is correct |
50 |
Correct |
80 ms |
10928 KB |
Output is correct |
51 |
Correct |
54 ms |
7596 KB |
Output is correct |
52 |
Correct |
73 ms |
11032 KB |
Output is correct |
53 |
Correct |
70 ms |
11148 KB |
Output is correct |
54 |
Correct |
95 ms |
11188 KB |
Output is correct |
55 |
Correct |
108 ms |
13176 KB |
Output is correct |