#include <bits/stdc++.h>
#define int int64_t
using namespace std;
vector<int>seg;
void update(int k, int v, int pos, int l, int r){
if(l == r){
seg[pos] = v;
return;
}
if(k <= (l+r)/2) update(k, v, pos*2, l, (l+r)/2);
else update(k, v, pos*2+1, (l+r)/2+1, r);
seg[pos] = max(seg[pos*2], seg[pos*2+1]);
}
int query(int ql, int qr, int pos, int l, int r){
if(l >= ql && r <= qr) return seg[pos];
else if(l > qr || r < ql) return 0;
else return max(query(ql, qr, pos*2, l, (l+r)/2), query(ql, qr, pos*2+1, (l+r)/2+1, r));
}
int bsearch(vector<int>&v, int val, int n){
int r = n-1;
int l = -1;
while(r-l > 1){
int x = (r+l)/2;
if(v[x] > val) r = x;
else l = x;
}
return v[r];
}
void print_tree(){
int cut = 1;
for(int i = 1; i<seg.size(); ++i){
cout<<seg[i]<<" ";
if(i == cut){
cut = cut*2+1;
cout<<endl;
}
}
cout<<endl<<endl;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, d; cin>>n>>d;
seg.assign(n*4, 0);
vector<int>v(n);
vector<int>fred(n);
for(int i = 0; i<n; ++i){
int a; cin>>a;
v[i] = a;
fred[i] = a;
}
//for(auto u: v) cout<<u<<" ";
//cout<<endl;
sort(fred.begin(), fred.end());
//for(auto u: fred) cout<<u<<" ";
//cout<<endl;
unordered_map<int, int>mp;
for(int i = 0; i<n; ++i){
mp[fred[i]] = i;
}
vector<int>lis(n);
for(int i = 0; i<n; ++i){
int cur;
if(mp[v[i]] == 0) cur = 1;
else cur = query(0, mp[v[i]]-1, 1, 0, n-1)+1;
lis[i] = cur;
update(mp[v[i]], cur, 1, 0, n-1);
}
//print_tree();
//for(auto u: lis) cout<<u<<" ";
//cout<<endl;
seg.assign(n*4, 0);
int ans = 0;
update(mp[v[n-1]], 1, 1, 0, n-1);
//print_tree();
for(int i = n-2; i>=0; --i){
int cur = bsearch(fred, v[i]-d, n);
//cout<<v[i]-d<<" "<<cur<<endl;
int suffix;
if(cur >= fred[n-1]) suffix = 0;
else suffix = query(mp[cur], n-1, 1, 0, n-1);
//cout<<suffix<<" "<<lis[i]<<" "<<i<<endl;
ans = max(ans, suffix+lis[i]);
int upd;
if(mp[v[i]] == n-1) upd = 1;
else upd = query(mp[v[i]]+1, n-1, 1, 0, n-1)+1;
update(mp[v[i]], upd, 1, 0, n-1);
//print_tree();
}
cout<<ans;
cout<<'\n';
}
Compilation message
glo.cpp: In function 'void print_tree()':
glo.cpp:40:18: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int i = 1; i<seg.size(); ++i){
| ~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
312 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
0 ms |
312 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
312 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
0 ms |
312 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
2 ms |
332 KB |
Output is correct |
20 |
Correct |
2 ms |
320 KB |
Output is correct |
21 |
Correct |
2 ms |
332 KB |
Output is correct |
22 |
Correct |
2 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
2 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
631 ms |
22204 KB |
Output is correct |
2 |
Correct |
596 ms |
22212 KB |
Output is correct |
3 |
Correct |
656 ms |
22228 KB |
Output is correct |
4 |
Correct |
639 ms |
22128 KB |
Output is correct |
5 |
Correct |
298 ms |
16952 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
98 ms |
5880 KB |
Output is correct |
2 |
Correct |
93 ms |
5716 KB |
Output is correct |
3 |
Correct |
98 ms |
5732 KB |
Output is correct |
4 |
Correct |
65 ms |
4416 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
61 ms |
4392 KB |
Output is correct |
7 |
Correct |
83 ms |
5720 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
186 ms |
11240 KB |
Output is correct |
2 |
Correct |
249 ms |
11240 KB |
Output is correct |
3 |
Correct |
513 ms |
22108 KB |
Output is correct |
4 |
Correct |
301 ms |
16828 KB |
Output is correct |
5 |
Correct |
115 ms |
10864 KB |
Output is correct |
6 |
Correct |
219 ms |
20624 KB |
Output is correct |
7 |
Correct |
225 ms |
21284 KB |
Output is correct |
8 |
Correct |
167 ms |
11260 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
312 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
0 ms |
312 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
2 ms |
332 KB |
Output is correct |
20 |
Correct |
2 ms |
320 KB |
Output is correct |
21 |
Correct |
2 ms |
332 KB |
Output is correct |
22 |
Correct |
2 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
2 ms |
332 KB |
Output is correct |
27 |
Correct |
631 ms |
22204 KB |
Output is correct |
28 |
Correct |
596 ms |
22212 KB |
Output is correct |
29 |
Correct |
656 ms |
22228 KB |
Output is correct |
30 |
Correct |
639 ms |
22128 KB |
Output is correct |
31 |
Correct |
298 ms |
16952 KB |
Output is correct |
32 |
Correct |
98 ms |
5880 KB |
Output is correct |
33 |
Correct |
93 ms |
5716 KB |
Output is correct |
34 |
Correct |
98 ms |
5732 KB |
Output is correct |
35 |
Correct |
65 ms |
4416 KB |
Output is correct |
36 |
Correct |
1 ms |
204 KB |
Output is correct |
37 |
Correct |
61 ms |
4392 KB |
Output is correct |
38 |
Correct |
83 ms |
5720 KB |
Output is correct |
39 |
Correct |
186 ms |
11240 KB |
Output is correct |
40 |
Correct |
249 ms |
11240 KB |
Output is correct |
41 |
Correct |
513 ms |
22108 KB |
Output is correct |
42 |
Correct |
301 ms |
16828 KB |
Output is correct |
43 |
Correct |
115 ms |
10864 KB |
Output is correct |
44 |
Correct |
219 ms |
20624 KB |
Output is correct |
45 |
Correct |
225 ms |
21284 KB |
Output is correct |
46 |
Correct |
167 ms |
11260 KB |
Output is correct |
47 |
Correct |
224 ms |
11252 KB |
Output is correct |
48 |
Correct |
225 ms |
11136 KB |
Output is correct |
49 |
Correct |
598 ms |
22168 KB |
Output is correct |
50 |
Correct |
282 ms |
16824 KB |
Output is correct |
51 |
Correct |
212 ms |
13872 KB |
Output is correct |
52 |
Correct |
312 ms |
21488 KB |
Output is correct |
53 |
Correct |
228 ms |
21516 KB |
Output is correct |
54 |
Correct |
240 ms |
22212 KB |
Output is correct |
55 |
Correct |
447 ms |
22236 KB |
Output is correct |