#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2e5+1;
const LL MOD = 1e9+7;
int a[N],dp[N][2],tree[N*4*3],b[N];
int n,k;
map<int,int>mp;
set<int>st;
void update(int v,int tl,int tr,int pos,int val){
if(tl==tr){
tree[v] = val;
return ;
}
int mid = (tl+tr)/2;
if(pos<=mid)update(v*2,tl,mid,pos,val);
else update(v*2+1,mid+1,tr,pos,val);
tree[v] = max(tree[v*2],tree[v*2+1]);
}
int get(int v,int tl,int tr,int l,int r){
if(tl>r||tr<l)
return 0;
if(tl>=l&&tr<=r)
return tree[v];
int mid = (tl+tr)/2;
return max(get(v*2,tl,mid,l,r),get(v*2+1,mid+1,tr,l,r));
}
void calc(){
for(int i=1;i<=n;i++){
dp[i][0] = get(1,1,3*n,1,b[i]-1)+1;
if(get(1,1,3*n,b[i],b[i])<dp[i][0])update(1,1,3*n,b[i],dp[i][0]);
}
for(int i=1;i<=n;i++)
update(1,1,3*n,b[i],0);
for(int i=n;i>=1;i--){
dp[i][1] = get(1,1,3*n,b[i]+1,3*n)+1;
if(get(1,1,3*n,b[i],b[i])<dp[i][1])update(1,1,3*n,b[i],dp[i][1]);
}
for(int i=1;i<=n;i++)
update(1,1,3*n,b[i],0);
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
st.insert(a[i]);
st.insert(max(0,a[i]-k+1));
st.insert(min((int)1e9,a[i]+k-1));
}
int cnt = 1;
for(auto x:st)
mp[x] = cnt++;
for(int i=1;i<=n;i++)
b[i] = mp[a[i]];
calc();
int ans = 0;
for(int i=n;i>=1;i--){
ans = max(ans,dp[i][0]+get(1,1,n*3,mp[max(0,a[i]-k+1)],mp[min(a[i]+k-1,(int)1e9)]));
if(get(1,1,3*n,b[i],b[i])<dp[i][1])
update(1,1,3*n,b[i],dp[i][1]);
}
printf("%d\n",ans);
}
Compilation message
glo.cpp: In function 'int main()':
glo.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
61 | scanf("%d%d",&n,&k);
| ~~~~~^~~~~~~~~~~~~~
glo.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | scanf("%d",&a[i]);
| ~~~~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 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 |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 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 |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
332 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 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 |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
332 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
3 ms |
588 KB |
Output is correct |
20 |
Correct |
3 ms |
588 KB |
Output is correct |
21 |
Correct |
2 ms |
588 KB |
Output is correct |
22 |
Correct |
2 ms |
588 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 |
332 KB |
Output is correct |
26 |
Correct |
3 ms |
464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1172 ms |
67956 KB |
Output is correct |
2 |
Correct |
1200 ms |
68044 KB |
Output is correct |
3 |
Correct |
1250 ms |
68064 KB |
Output is correct |
4 |
Correct |
1158 ms |
67912 KB |
Output is correct |
5 |
Correct |
446 ms |
35640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
211 ms |
17228 KB |
Output is correct |
2 |
Correct |
198 ms |
17132 KB |
Output is correct |
3 |
Correct |
206 ms |
17220 KB |
Output is correct |
4 |
Correct |
103 ms |
9184 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
92 ms |
3784 KB |
Output is correct |
7 |
Correct |
154 ms |
13628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
279 ms |
12648 KB |
Output is correct |
2 |
Correct |
301 ms |
12720 KB |
Output is correct |
3 |
Correct |
638 ms |
24996 KB |
Output is correct |
4 |
Correct |
378 ms |
14240 KB |
Output is correct |
5 |
Correct |
219 ms |
12612 KB |
Output is correct |
6 |
Correct |
451 ms |
23908 KB |
Output is correct |
7 |
Correct |
462 ms |
23908 KB |
Output is correct |
8 |
Correct |
260 ms |
12712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 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 |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
332 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
3 ms |
588 KB |
Output is correct |
20 |
Correct |
3 ms |
588 KB |
Output is correct |
21 |
Correct |
2 ms |
588 KB |
Output is correct |
22 |
Correct |
2 ms |
588 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 |
332 KB |
Output is correct |
26 |
Correct |
3 ms |
464 KB |
Output is correct |
27 |
Correct |
1172 ms |
67956 KB |
Output is correct |
28 |
Correct |
1200 ms |
68044 KB |
Output is correct |
29 |
Correct |
1250 ms |
68064 KB |
Output is correct |
30 |
Correct |
1158 ms |
67912 KB |
Output is correct |
31 |
Correct |
446 ms |
35640 KB |
Output is correct |
32 |
Correct |
211 ms |
17228 KB |
Output is correct |
33 |
Correct |
198 ms |
17132 KB |
Output is correct |
34 |
Correct |
206 ms |
17220 KB |
Output is correct |
35 |
Correct |
103 ms |
9184 KB |
Output is correct |
36 |
Correct |
0 ms |
204 KB |
Output is correct |
37 |
Correct |
92 ms |
3784 KB |
Output is correct |
38 |
Correct |
154 ms |
13628 KB |
Output is correct |
39 |
Correct |
279 ms |
12648 KB |
Output is correct |
40 |
Correct |
301 ms |
12720 KB |
Output is correct |
41 |
Correct |
638 ms |
24996 KB |
Output is correct |
42 |
Correct |
378 ms |
14240 KB |
Output is correct |
43 |
Correct |
219 ms |
12612 KB |
Output is correct |
44 |
Correct |
451 ms |
23908 KB |
Output is correct |
45 |
Correct |
462 ms |
23908 KB |
Output is correct |
46 |
Correct |
260 ms |
12712 KB |
Output is correct |
47 |
Correct |
509 ms |
34068 KB |
Output is correct |
48 |
Correct |
480 ms |
34184 KB |
Output is correct |
49 |
Correct |
1256 ms |
67988 KB |
Output is correct |
50 |
Correct |
524 ms |
35800 KB |
Output is correct |
51 |
Correct |
315 ms |
17724 KB |
Output is correct |
52 |
Correct |
503 ms |
25080 KB |
Output is correct |
53 |
Correct |
474 ms |
25000 KB |
Output is correct |
54 |
Correct |
446 ms |
24944 KB |
Output is correct |
55 |
Correct |
773 ms |
53804 KB |
Output is correct |