#include <bits/stdc++.h>
using namespace std;
const int MX=200010, inf=2e9+1;
int n, A[MX], x, lim;
vector<int> X={-inf};
struct Seg{
int tree[1<<19]={};
void upt(int v, int s, int e, int x, int val){
if(x<s || e<x) return;
if(s==e){ tree[v]=val; return; }
upt(v*2,s,(s+e)/2,x,val);
upt(v*2+1,(s+e)/2+1,e,x,val);
tree[v]=max(tree[v*2],tree[v*2+1]);
}
void upt(int x, int v){
upt(1,0,lim,x,v);
}
int mx(int v, int s, int e, int r){
if(e<=r) return tree[v];
int m=(s+e)/2;
if(r<=m) return mx(v*2,s,m,r);
else return max(mx(v*2,s,m,r), mx(v*2+1,m+1,e,r));
}
int mx(int r){
return mx(1,0,lim,r);
}
int val(int v, int s, int e, int x){
if(x<s || e<x) return 0;
if(s==e) return tree[v];
return max(val(v*2,s,(s+e)/2,x), val(v*2+1,(s+e)/2+1,e,x));
}
} S1, S2;
int find(int x){
return upper_bound(X.begin(), X.end(), x)-X.begin()-1;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>x;
for(int i=1; i<=n; i++) cin>>A[i], X.push_back(A[i]);
sort(X.begin(), X.end());
lim=unique(X.begin(), X.end())-X.begin();
X.resize(lim); lim--;
for(int i=1; i<=n; i++){
int p1=find(A[i]-1), p2=find(A[i]+x-1), p3=find(A[i]);
int a=S1.mx(p1), b=S2.mx(p1), c=S1.mx(p2);
S1.upt(p3, a+1);
S2.upt(p3, max(b+1, c+1));
/* for(int j=1; j<=lim; j++) cout<<S1.val(1,0,lim,j)<<' ';
cout<<'\n';
for(int j=1; j<=lim; j++) cout<<S2.val(1,0,lim,j)<<' ';
cout<<'\n';
cout<<'\n';
*/
}
cout<<S2.mx(lim)<<'\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
252 KB |
Output is correct |
2 |
Correct |
2 ms |
356 KB |
Output is correct |
3 |
Correct |
2 ms |
392 KB |
Output is correct |
4 |
Correct |
3 ms |
468 KB |
Output is correct |
5 |
Correct |
3 ms |
540 KB |
Output is correct |
6 |
Correct |
2 ms |
620 KB |
Output is correct |
7 |
Correct |
3 ms |
620 KB |
Output is correct |
8 |
Correct |
2 ms |
620 KB |
Output is correct |
9 |
Correct |
3 ms |
620 KB |
Output is correct |
10 |
Correct |
2 ms |
620 KB |
Output is correct |
11 |
Correct |
2 ms |
620 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
252 KB |
Output is correct |
2 |
Correct |
2 ms |
356 KB |
Output is correct |
3 |
Correct |
2 ms |
392 KB |
Output is correct |
4 |
Correct |
3 ms |
468 KB |
Output is correct |
5 |
Correct |
3 ms |
540 KB |
Output is correct |
6 |
Correct |
2 ms |
620 KB |
Output is correct |
7 |
Correct |
3 ms |
620 KB |
Output is correct |
8 |
Correct |
2 ms |
620 KB |
Output is correct |
9 |
Correct |
3 ms |
620 KB |
Output is correct |
10 |
Correct |
2 ms |
620 KB |
Output is correct |
11 |
Correct |
2 ms |
620 KB |
Output is correct |
12 |
Correct |
2 ms |
620 KB |
Output is correct |
13 |
Correct |
2 ms |
620 KB |
Output is correct |
14 |
Correct |
3 ms |
636 KB |
Output is correct |
15 |
Correct |
3 ms |
636 KB |
Output is correct |
16 |
Correct |
2 ms |
636 KB |
Output is correct |
17 |
Correct |
3 ms |
636 KB |
Output is correct |
18 |
Correct |
3 ms |
636 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
252 KB |
Output is correct |
2 |
Correct |
2 ms |
356 KB |
Output is correct |
3 |
Correct |
2 ms |
392 KB |
Output is correct |
4 |
Correct |
3 ms |
468 KB |
Output is correct |
5 |
Correct |
3 ms |
540 KB |
Output is correct |
6 |
Correct |
2 ms |
620 KB |
Output is correct |
7 |
Correct |
3 ms |
620 KB |
Output is correct |
8 |
Correct |
2 ms |
620 KB |
Output is correct |
9 |
Correct |
3 ms |
620 KB |
Output is correct |
10 |
Correct |
2 ms |
620 KB |
Output is correct |
11 |
Correct |
2 ms |
620 KB |
Output is correct |
12 |
Correct |
2 ms |
620 KB |
Output is correct |
13 |
Correct |
2 ms |
620 KB |
Output is correct |
14 |
Correct |
3 ms |
636 KB |
Output is correct |
15 |
Correct |
3 ms |
636 KB |
Output is correct |
16 |
Correct |
2 ms |
636 KB |
Output is correct |
17 |
Correct |
3 ms |
636 KB |
Output is correct |
18 |
Correct |
3 ms |
636 KB |
Output is correct |
19 |
Correct |
3 ms |
636 KB |
Output is correct |
20 |
Correct |
4 ms |
636 KB |
Output is correct |
21 |
Correct |
4 ms |
636 KB |
Output is correct |
22 |
Correct |
5 ms |
636 KB |
Output is correct |
23 |
Correct |
3 ms |
636 KB |
Output is correct |
24 |
Correct |
3 ms |
636 KB |
Output is correct |
25 |
Correct |
2 ms |
636 KB |
Output is correct |
26 |
Correct |
3 ms |
636 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
384 ms |
6516 KB |
Output is correct |
2 |
Correct |
399 ms |
6516 KB |
Output is correct |
3 |
Correct |
338 ms |
6516 KB |
Output is correct |
4 |
Correct |
347 ms |
6516 KB |
Output is correct |
5 |
Correct |
130 ms |
6516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
74 ms |
6516 KB |
Output is correct |
2 |
Correct |
79 ms |
6516 KB |
Output is correct |
3 |
Correct |
77 ms |
6516 KB |
Output is correct |
4 |
Correct |
41 ms |
6516 KB |
Output is correct |
5 |
Correct |
2 ms |
6516 KB |
Output is correct |
6 |
Correct |
39 ms |
6516 KB |
Output is correct |
7 |
Correct |
65 ms |
6516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
152 ms |
6516 KB |
Output is correct |
2 |
Correct |
151 ms |
6516 KB |
Output is correct |
3 |
Correct |
339 ms |
6516 KB |
Output is correct |
4 |
Correct |
133 ms |
6516 KB |
Output is correct |
5 |
Correct |
82 ms |
6516 KB |
Output is correct |
6 |
Correct |
144 ms |
6516 KB |
Output is correct |
7 |
Correct |
147 ms |
6516 KB |
Output is correct |
8 |
Correct |
113 ms |
6516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
252 KB |
Output is correct |
2 |
Correct |
2 ms |
356 KB |
Output is correct |
3 |
Correct |
2 ms |
392 KB |
Output is correct |
4 |
Correct |
3 ms |
468 KB |
Output is correct |
5 |
Correct |
3 ms |
540 KB |
Output is correct |
6 |
Correct |
2 ms |
620 KB |
Output is correct |
7 |
Correct |
3 ms |
620 KB |
Output is correct |
8 |
Correct |
2 ms |
620 KB |
Output is correct |
9 |
Correct |
3 ms |
620 KB |
Output is correct |
10 |
Correct |
2 ms |
620 KB |
Output is correct |
11 |
Correct |
2 ms |
620 KB |
Output is correct |
12 |
Correct |
2 ms |
620 KB |
Output is correct |
13 |
Correct |
2 ms |
620 KB |
Output is correct |
14 |
Correct |
3 ms |
636 KB |
Output is correct |
15 |
Correct |
3 ms |
636 KB |
Output is correct |
16 |
Correct |
2 ms |
636 KB |
Output is correct |
17 |
Correct |
3 ms |
636 KB |
Output is correct |
18 |
Correct |
3 ms |
636 KB |
Output is correct |
19 |
Correct |
3 ms |
636 KB |
Output is correct |
20 |
Correct |
4 ms |
636 KB |
Output is correct |
21 |
Correct |
4 ms |
636 KB |
Output is correct |
22 |
Correct |
5 ms |
636 KB |
Output is correct |
23 |
Correct |
3 ms |
636 KB |
Output is correct |
24 |
Correct |
3 ms |
636 KB |
Output is correct |
25 |
Correct |
2 ms |
636 KB |
Output is correct |
26 |
Correct |
3 ms |
636 KB |
Output is correct |
27 |
Correct |
384 ms |
6516 KB |
Output is correct |
28 |
Correct |
399 ms |
6516 KB |
Output is correct |
29 |
Correct |
338 ms |
6516 KB |
Output is correct |
30 |
Correct |
347 ms |
6516 KB |
Output is correct |
31 |
Correct |
130 ms |
6516 KB |
Output is correct |
32 |
Correct |
74 ms |
6516 KB |
Output is correct |
33 |
Correct |
79 ms |
6516 KB |
Output is correct |
34 |
Correct |
77 ms |
6516 KB |
Output is correct |
35 |
Correct |
41 ms |
6516 KB |
Output is correct |
36 |
Correct |
2 ms |
6516 KB |
Output is correct |
37 |
Correct |
39 ms |
6516 KB |
Output is correct |
38 |
Correct |
65 ms |
6516 KB |
Output is correct |
39 |
Correct |
152 ms |
6516 KB |
Output is correct |
40 |
Correct |
151 ms |
6516 KB |
Output is correct |
41 |
Correct |
339 ms |
6516 KB |
Output is correct |
42 |
Correct |
133 ms |
6516 KB |
Output is correct |
43 |
Correct |
82 ms |
6516 KB |
Output is correct |
44 |
Correct |
144 ms |
6516 KB |
Output is correct |
45 |
Correct |
147 ms |
6516 KB |
Output is correct |
46 |
Correct |
113 ms |
6516 KB |
Output is correct |
47 |
Correct |
161 ms |
6516 KB |
Output is correct |
48 |
Correct |
167 ms |
6516 KB |
Output is correct |
49 |
Correct |
402 ms |
6516 KB |
Output is correct |
50 |
Correct |
162 ms |
6516 KB |
Output is correct |
51 |
Correct |
153 ms |
6516 KB |
Output is correct |
52 |
Correct |
219 ms |
6516 KB |
Output is correct |
53 |
Correct |
169 ms |
6516 KB |
Output is correct |
54 |
Correct |
184 ms |
6516 KB |
Output is correct |
55 |
Correct |
302 ms |
6516 KB |
Output is correct |