#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const int N = (1 << 19) ;
int n, d, ans, dp[N + 1], p[N + 1], kol[N + 1], mn[2 * N + 1], mx[2 * N + 1] ;
pair<int, int> a[N + 1] ;
int get(int a)
{
while(a != p[a])
a = p[a] ;
return a ;
}
void join(int a, int b)
{
a = get(a) ;
b = get(b) ;
if(a == b)
return ;
if(kol[a] > kol[b])
swap(a, b) ;
mn[b] = min(mn[a], mn[b]) ;
kol[b] += kol[a] ;
kol[a] = 0 ;
p[a] = b ;
}
int get_min(int a)
{
a = get(a) ;
return mn[a] ;
}
void update(int l, int r, int ind, int num, int v)
{
if(l > ind || r < ind)
return ;
if(l == r)
{
mx[v] = num ;
return ;
}
int mid = (l + r) >> 1 ;
update(l, mid, ind, num, v * 2) ;
update(mid + 1, r, ind, num, v * 2 + 1) ;
mx[v] = max(mx[v * 2], mx[v * 2 + 1]) ;
}
int get_max(int l, int r, int l1, int r1, int v)
{
if(l > r1 || r < l1)
return 0 ;
if(l1 <= l && r <= r1)
return mx[v] ;
int mid = (l + r) >> 1 ;
return max(get_max(l, mid, l1, r1, v * 2), get_max(mid + 1, r, l1, r1, v * 2 + 1)) ;
}
bool cmp(pair<int, int> p1, pair<int, int> p2)
{
if(p1.fi != p2.fi)
return p1.fi < p2.fi ;
else
return p1.se > p2.se ;
}
signed main()
{
ios_base::sync_with_stdio( 0 ) ;
cin.tie( 0 ) ;
cout.tie( 0 ) ;
cin >> n >> d ;
for(int i = 1 ; i <= n ; i++)
{
cin >> a[i].fi ;
p[i] = i ;
mn[i] = i ;
kol[i] = 1 ;
a[i].se = i ;
}
sort(a + 1, a + n + 1, cmp) ;
set<int> all ;
for(int i = 1 ; i <= n ; i++)
{
auto it = all.lower_bound(a[i].se) ;
if(it != all.end() && *it - d <= a[i].se)
{
join(*it, a[i].se) ;
// cout<<"join{"<<*it<<' ' <<a[i].se<<"}\n" ;
}
if(it != all.begin() && *--it + d >= a[i].se)
{
join(*it, a[i].se) ;
// cout<<"join{"<<*it<<' '<<a[i].se<<"}\n" ;
}
int num = get_max(1, N, get_min(a[i].se), a[i].se, 1) ;
dp[a[i].se] = num + 1 ;
update(1, N, a[i].se, num + 1, 1) ;
// cout << get_min(a[i].se) << ' ' << a[i].se << ' ' << dp[a[i].se] << '\n' ;
ans = max(ans, dp[a[i].se]) ;
all.insert(a[i].se) ;
}
cout << ans ;
return 0 ;
}
//13 2
//27 1 23 13 1 10 25 0 27 18 29 16 8
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
328 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
332 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
0 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
328 KB |
Output is correct |
24 |
Correct |
0 ms |
340 KB |
Output is correct |
25 |
Correct |
0 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
328 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
332 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
0 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
328 KB |
Output is correct |
24 |
Correct |
0 ms |
340 KB |
Output is correct |
25 |
Correct |
0 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
328 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
340 KB |
Output is correct |
38 |
Correct |
1 ms |
340 KB |
Output is correct |
39 |
Correct |
1 ms |
340 KB |
Output is correct |
40 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
328 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
332 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
0 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
328 KB |
Output is correct |
24 |
Correct |
0 ms |
340 KB |
Output is correct |
25 |
Correct |
0 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
328 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
340 KB |
Output is correct |
38 |
Correct |
1 ms |
340 KB |
Output is correct |
39 |
Correct |
1 ms |
340 KB |
Output is correct |
40 |
Correct |
1 ms |
340 KB |
Output is correct |
41 |
Correct |
6 ms |
980 KB |
Output is correct |
42 |
Correct |
5 ms |
964 KB |
Output is correct |
43 |
Correct |
5 ms |
948 KB |
Output is correct |
44 |
Correct |
5 ms |
856 KB |
Output is correct |
45 |
Correct |
5 ms |
848 KB |
Output is correct |
46 |
Correct |
6 ms |
980 KB |
Output is correct |
47 |
Correct |
5 ms |
956 KB |
Output is correct |
48 |
Correct |
5 ms |
980 KB |
Output is correct |
49 |
Correct |
5 ms |
980 KB |
Output is correct |
50 |
Correct |
5 ms |
980 KB |
Output is correct |
51 |
Correct |
5 ms |
980 KB |
Output is correct |
52 |
Correct |
5 ms |
980 KB |
Output is correct |
53 |
Correct |
4 ms |
980 KB |
Output is correct |
54 |
Correct |
5 ms |
976 KB |
Output is correct |
55 |
Correct |
5 ms |
976 KB |
Output is correct |
56 |
Correct |
5 ms |
980 KB |
Output is correct |
57 |
Correct |
5 ms |
976 KB |
Output is correct |
58 |
Correct |
4 ms |
972 KB |
Output is correct |
59 |
Correct |
4 ms |
980 KB |
Output is correct |
60 |
Correct |
4 ms |
980 KB |
Output is correct |
61 |
Correct |
5 ms |
980 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
191 ms |
23752 KB |
Output is correct |
2 |
Correct |
211 ms |
26304 KB |
Output is correct |
3 |
Correct |
299 ms |
26752 KB |
Output is correct |
4 |
Correct |
352 ms |
26644 KB |
Output is correct |
5 |
Correct |
291 ms |
26832 KB |
Output is correct |
6 |
Correct |
339 ms |
26696 KB |
Output is correct |
7 |
Correct |
186 ms |
26472 KB |
Output is correct |
8 |
Correct |
192 ms |
26664 KB |
Output is correct |
9 |
Correct |
175 ms |
26644 KB |
Output is correct |
10 |
Correct |
180 ms |
26700 KB |
Output is correct |
11 |
Correct |
252 ms |
26712 KB |
Output is correct |
12 |
Correct |
274 ms |
26752 KB |
Output is correct |
13 |
Correct |
315 ms |
26712 KB |
Output is correct |
14 |
Correct |
349 ms |
26804 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
191 ms |
23772 KB |
Output is correct |
2 |
Correct |
281 ms |
25588 KB |
Output is correct |
3 |
Correct |
337 ms |
26700 KB |
Output is correct |
4 |
Correct |
349 ms |
26728 KB |
Output is correct |
5 |
Correct |
328 ms |
26712 KB |
Output is correct |
6 |
Correct |
346 ms |
26756 KB |
Output is correct |
7 |
Correct |
194 ms |
26640 KB |
Output is correct |
8 |
Correct |
190 ms |
26780 KB |
Output is correct |
9 |
Correct |
184 ms |
26468 KB |
Output is correct |
10 |
Correct |
247 ms |
26704 KB |
Output is correct |
11 |
Correct |
316 ms |
26700 KB |
Output is correct |
12 |
Correct |
327 ms |
26640 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
328 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
332 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
0 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
328 KB |
Output is correct |
24 |
Correct |
0 ms |
340 KB |
Output is correct |
25 |
Correct |
0 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
328 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
340 KB |
Output is correct |
38 |
Correct |
1 ms |
340 KB |
Output is correct |
39 |
Correct |
1 ms |
340 KB |
Output is correct |
40 |
Correct |
1 ms |
340 KB |
Output is correct |
41 |
Correct |
6 ms |
980 KB |
Output is correct |
42 |
Correct |
5 ms |
964 KB |
Output is correct |
43 |
Correct |
5 ms |
948 KB |
Output is correct |
44 |
Correct |
5 ms |
856 KB |
Output is correct |
45 |
Correct |
5 ms |
848 KB |
Output is correct |
46 |
Correct |
6 ms |
980 KB |
Output is correct |
47 |
Correct |
5 ms |
956 KB |
Output is correct |
48 |
Correct |
5 ms |
980 KB |
Output is correct |
49 |
Correct |
5 ms |
980 KB |
Output is correct |
50 |
Correct |
5 ms |
980 KB |
Output is correct |
51 |
Correct |
5 ms |
980 KB |
Output is correct |
52 |
Correct |
5 ms |
980 KB |
Output is correct |
53 |
Correct |
4 ms |
980 KB |
Output is correct |
54 |
Correct |
5 ms |
976 KB |
Output is correct |
55 |
Correct |
5 ms |
976 KB |
Output is correct |
56 |
Correct |
5 ms |
980 KB |
Output is correct |
57 |
Correct |
5 ms |
976 KB |
Output is correct |
58 |
Correct |
4 ms |
972 KB |
Output is correct |
59 |
Correct |
4 ms |
980 KB |
Output is correct |
60 |
Correct |
4 ms |
980 KB |
Output is correct |
61 |
Correct |
5 ms |
980 KB |
Output is correct |
62 |
Correct |
191 ms |
23752 KB |
Output is correct |
63 |
Correct |
211 ms |
26304 KB |
Output is correct |
64 |
Correct |
299 ms |
26752 KB |
Output is correct |
65 |
Correct |
352 ms |
26644 KB |
Output is correct |
66 |
Correct |
291 ms |
26832 KB |
Output is correct |
67 |
Correct |
339 ms |
26696 KB |
Output is correct |
68 |
Correct |
186 ms |
26472 KB |
Output is correct |
69 |
Correct |
192 ms |
26664 KB |
Output is correct |
70 |
Correct |
175 ms |
26644 KB |
Output is correct |
71 |
Correct |
180 ms |
26700 KB |
Output is correct |
72 |
Correct |
252 ms |
26712 KB |
Output is correct |
73 |
Correct |
274 ms |
26752 KB |
Output is correct |
74 |
Correct |
315 ms |
26712 KB |
Output is correct |
75 |
Correct |
349 ms |
26804 KB |
Output is correct |
76 |
Correct |
191 ms |
23772 KB |
Output is correct |
77 |
Correct |
281 ms |
25588 KB |
Output is correct |
78 |
Correct |
337 ms |
26700 KB |
Output is correct |
79 |
Correct |
349 ms |
26728 KB |
Output is correct |
80 |
Correct |
328 ms |
26712 KB |
Output is correct |
81 |
Correct |
346 ms |
26756 KB |
Output is correct |
82 |
Correct |
194 ms |
26640 KB |
Output is correct |
83 |
Correct |
190 ms |
26780 KB |
Output is correct |
84 |
Correct |
184 ms |
26468 KB |
Output is correct |
85 |
Correct |
247 ms |
26704 KB |
Output is correct |
86 |
Correct |
316 ms |
26700 KB |
Output is correct |
87 |
Correct |
327 ms |
26640 KB |
Output is correct |
88 |
Correct |
352 ms |
26752 KB |
Output is correct |
89 |
Correct |
357 ms |
26824 KB |
Output is correct |
90 |
Correct |
372 ms |
26632 KB |
Output is correct |
91 |
Correct |
376 ms |
26696 KB |
Output is correct |
92 |
Correct |
247 ms |
26700 KB |
Output is correct |
93 |
Correct |
357 ms |
26688 KB |
Output is correct |
94 |
Correct |
367 ms |
26684 KB |
Output is correct |
95 |
Correct |
303 ms |
26640 KB |
Output is correct |
96 |
Correct |
370 ms |
26676 KB |
Output is correct |
97 |
Correct |
355 ms |
26644 KB |
Output is correct |
98 |
Correct |
389 ms |
26816 KB |
Output is correct |
99 |
Correct |
351 ms |
26700 KB |
Output is correct |
100 |
Correct |
352 ms |
26736 KB |
Output is correct |
101 |
Correct |
179 ms |
26700 KB |
Output is correct |
102 |
Correct |
205 ms |
26640 KB |
Output is correct |
103 |
Correct |
204 ms |
26656 KB |
Output is correct |
104 |
Correct |
222 ms |
26692 KB |
Output is correct |
105 |
Correct |
260 ms |
26716 KB |
Output is correct |
106 |
Correct |
249 ms |
26840 KB |
Output is correct |
107 |
Correct |
291 ms |
26648 KB |
Output is correct |
108 |
Correct |
348 ms |
26648 KB |
Output is correct |
109 |
Correct |
268 ms |
26756 KB |
Output is correct |
110 |
Correct |
340 ms |
26660 KB |
Output is correct |
111 |
Correct |
367 ms |
26736 KB |
Output is correct |
112 |
Correct |
232 ms |
26696 KB |
Output is correct |
113 |
Correct |
328 ms |
26772 KB |
Output is correct |
114 |
Correct |
354 ms |
26672 KB |
Output is correct |
115 |
Correct |
195 ms |
26796 KB |
Output is correct |
116 |
Correct |
205 ms |
26720 KB |
Output is correct |
117 |
Correct |
251 ms |
26648 KB |
Output is correct |
118 |
Correct |
246 ms |
26724 KB |
Output is correct |
119 |
Correct |
231 ms |
26628 KB |
Output is correct |
120 |
Correct |
224 ms |
26700 KB |
Output is correct |