#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const int N = (1 << 19), NS = 7000 ;
int n, d, cnt, a[N + 1], dp[N + 1], mx[2 * N + 1] ;
set<int> s ;
map<int, int> mp ;
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)) ;
}
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] ;
s.insert(a[i]) ;
}
for(int i : s)
{
cnt++ ;
mp[i] = cnt ;
}
for(int i = 1 ; i <= n ; i++)
a[i] = mp[a[i]] ;
if(n <= 400)
{
int ans = 0 ;
for(int i = n ; i >= 1 ; i--)
{
int mx = 0 ;
for(int j = i + 1 ; j <= n ; j++)
if(a[j] > a[i])
{
bool flag = 0 ;
vector<int> v ;
v.push_back(i) ;
for(int q = i + 1 ; q <= j ; q++)
if(a[q] < a[j])
{
if(q - v.back() > d)
flag = 1 ;
v.push_back(q) ;
}
if(j - v.back() > d)
flag = 1 ;
if(!flag)
mx = max(mx, dp[j]) ;
}
dp[i] = mx + 1 ;
ans = max(ans, dp[i]) ;
}
cout << ans ;
return 0 ;
}
if(n <= 7000)
{
int ans = 0 ;
for(int i = n ; i >= 1 ; i--)
{
int ls = i ;
dp[i] = max(dp[i], 1) ;
for(int j = i - 1 ; j >= 1 ; j--)
{
if(ls - j > d)
break ;
if(a[j] < a[i])
{
ls = j ;
dp[j] = max(dp[j], dp[i] + 1) ;
}
}
ans = max(ans, dp[i]) ;
}
cout << ans ;
return 0 ;
}
if(d == 1)
{
int ans = 0 ;
for(int i = 1 ; i <= n ; i++)
update(1, N, i, a[i], 1) ;
for(int i = n ; i >= 1 ; i--)
{
int l = i, r = n + 1 ;
while(l + 1 < r)
{
int mid = (l + r) >> 1 ;
if(get_max(1, N, i, mid, 1) > a[i])
r = mid ;
else
l = mid ;
}
dp[i] = dp[r] + 1 ;
ans = max(ans, dp[i]) ;
}
cout << ans ;
return 0 ;
}
if(d == n)
{
int ans = 0 ;
for(int i = 1 ; i <= n ; i++)
{
int num = get_max(1, N, 1, a[i] - 1, 1) ;
ans = max(ans, num + 1) ;
update(1, N, a[i], num + 1, 1) ;
}
cout << ans ;
return 0 ;
}
return 0 ;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
328 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 |
328 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 |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
328 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
324 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
328 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 |
328 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 |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
328 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
324 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
0 ms |
340 KB |
Output is correct |
27 |
Correct |
27 ms |
388 KB |
Output is correct |
28 |
Correct |
27 ms |
388 KB |
Output is correct |
29 |
Correct |
21 ms |
356 KB |
Output is correct |
30 |
Correct |
21 ms |
340 KB |
Output is correct |
31 |
Correct |
10 ms |
324 KB |
Output is correct |
32 |
Correct |
24 ms |
340 KB |
Output is correct |
33 |
Correct |
28 ms |
368 KB |
Output is correct |
34 |
Correct |
28 ms |
340 KB |
Output is correct |
35 |
Correct |
30 ms |
340 KB |
Output is correct |
36 |
Correct |
28 ms |
340 KB |
Output is correct |
37 |
Correct |
39 ms |
340 KB |
Output is correct |
38 |
Correct |
39 ms |
372 KB |
Output is correct |
39 |
Correct |
22 ms |
340 KB |
Output is correct |
40 |
Correct |
19 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
328 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 |
328 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 |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
328 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
324 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
0 ms |
340 KB |
Output is correct |
27 |
Correct |
27 ms |
388 KB |
Output is correct |
28 |
Correct |
27 ms |
388 KB |
Output is correct |
29 |
Correct |
21 ms |
356 KB |
Output is correct |
30 |
Correct |
21 ms |
340 KB |
Output is correct |
31 |
Correct |
10 ms |
324 KB |
Output is correct |
32 |
Correct |
24 ms |
340 KB |
Output is correct |
33 |
Correct |
28 ms |
368 KB |
Output is correct |
34 |
Correct |
28 ms |
340 KB |
Output is correct |
35 |
Correct |
30 ms |
340 KB |
Output is correct |
36 |
Correct |
28 ms |
340 KB |
Output is correct |
37 |
Correct |
39 ms |
340 KB |
Output is correct |
38 |
Correct |
39 ms |
372 KB |
Output is correct |
39 |
Correct |
22 ms |
340 KB |
Output is correct |
40 |
Correct |
19 ms |
340 KB |
Output is correct |
41 |
Correct |
3 ms |
596 KB |
Output is correct |
42 |
Correct |
5 ms |
1108 KB |
Output is correct |
43 |
Correct |
4 ms |
340 KB |
Output is correct |
44 |
Correct |
44 ms |
724 KB |
Output is correct |
45 |
Correct |
65 ms |
724 KB |
Output is correct |
46 |
Correct |
75 ms |
1092 KB |
Output is correct |
47 |
Correct |
27 ms |
980 KB |
Output is correct |
48 |
Correct |
24 ms |
1108 KB |
Output is correct |
49 |
Correct |
33 ms |
1108 KB |
Output is correct |
50 |
Correct |
50 ms |
1108 KB |
Output is correct |
51 |
Correct |
4 ms |
1084 KB |
Output is correct |
52 |
Correct |
6 ms |
1108 KB |
Output is correct |
53 |
Correct |
32 ms |
1108 KB |
Output is correct |
54 |
Correct |
45 ms |
1104 KB |
Output is correct |
55 |
Correct |
64 ms |
1108 KB |
Output is correct |
56 |
Correct |
49 ms |
1108 KB |
Output is correct |
57 |
Correct |
40 ms |
1108 KB |
Output is correct |
58 |
Correct |
24 ms |
1108 KB |
Output is correct |
59 |
Correct |
33 ms |
1108 KB |
Output is correct |
60 |
Correct |
25 ms |
980 KB |
Output is correct |
61 |
Correct |
39 ms |
1108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1241 ms |
7924 KB |
Output is correct |
2 |
Correct |
1167 ms |
7528 KB |
Output is correct |
3 |
Correct |
1150 ms |
7856 KB |
Output is correct |
4 |
Correct |
2069 ms |
31876 KB |
Output is correct |
5 |
Correct |
1559 ms |
36152 KB |
Output is correct |
6 |
Correct |
1376 ms |
36020 KB |
Output is correct |
7 |
Correct |
1124 ms |
35796 KB |
Output is correct |
8 |
Correct |
1288 ms |
35960 KB |
Output is correct |
9 |
Correct |
1135 ms |
36112 KB |
Output is correct |
10 |
Correct |
1243 ms |
36288 KB |
Output is correct |
11 |
Correct |
1209 ms |
36060 KB |
Output is correct |
12 |
Correct |
1203 ms |
36112 KB |
Output is correct |
13 |
Correct |
1204 ms |
36112 KB |
Output is correct |
14 |
Correct |
1341 ms |
36068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
65 ms |
4684 KB |
Output is correct |
2 |
Correct |
98 ms |
4396 KB |
Output is correct |
3 |
Correct |
141 ms |
4808 KB |
Output is correct |
4 |
Correct |
400 ms |
34948 KB |
Output is correct |
5 |
Correct |
355 ms |
34968 KB |
Output is correct |
6 |
Correct |
383 ms |
34964 KB |
Output is correct |
7 |
Correct |
219 ms |
34892 KB |
Output is correct |
8 |
Correct |
222 ms |
34976 KB |
Output is correct |
9 |
Correct |
223 ms |
34696 KB |
Output is correct |
10 |
Correct |
285 ms |
34876 KB |
Output is correct |
11 |
Correct |
385 ms |
34904 KB |
Output is correct |
12 |
Correct |
315 ms |
34940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
328 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 |
328 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 |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
328 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
324 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
0 ms |
340 KB |
Output is correct |
27 |
Correct |
27 ms |
388 KB |
Output is correct |
28 |
Correct |
27 ms |
388 KB |
Output is correct |
29 |
Correct |
21 ms |
356 KB |
Output is correct |
30 |
Correct |
21 ms |
340 KB |
Output is correct |
31 |
Correct |
10 ms |
324 KB |
Output is correct |
32 |
Correct |
24 ms |
340 KB |
Output is correct |
33 |
Correct |
28 ms |
368 KB |
Output is correct |
34 |
Correct |
28 ms |
340 KB |
Output is correct |
35 |
Correct |
30 ms |
340 KB |
Output is correct |
36 |
Correct |
28 ms |
340 KB |
Output is correct |
37 |
Correct |
39 ms |
340 KB |
Output is correct |
38 |
Correct |
39 ms |
372 KB |
Output is correct |
39 |
Correct |
22 ms |
340 KB |
Output is correct |
40 |
Correct |
19 ms |
340 KB |
Output is correct |
41 |
Correct |
3 ms |
596 KB |
Output is correct |
42 |
Correct |
5 ms |
1108 KB |
Output is correct |
43 |
Correct |
4 ms |
340 KB |
Output is correct |
44 |
Correct |
44 ms |
724 KB |
Output is correct |
45 |
Correct |
65 ms |
724 KB |
Output is correct |
46 |
Correct |
75 ms |
1092 KB |
Output is correct |
47 |
Correct |
27 ms |
980 KB |
Output is correct |
48 |
Correct |
24 ms |
1108 KB |
Output is correct |
49 |
Correct |
33 ms |
1108 KB |
Output is correct |
50 |
Correct |
50 ms |
1108 KB |
Output is correct |
51 |
Correct |
4 ms |
1084 KB |
Output is correct |
52 |
Correct |
6 ms |
1108 KB |
Output is correct |
53 |
Correct |
32 ms |
1108 KB |
Output is correct |
54 |
Correct |
45 ms |
1104 KB |
Output is correct |
55 |
Correct |
64 ms |
1108 KB |
Output is correct |
56 |
Correct |
49 ms |
1108 KB |
Output is correct |
57 |
Correct |
40 ms |
1108 KB |
Output is correct |
58 |
Correct |
24 ms |
1108 KB |
Output is correct |
59 |
Correct |
33 ms |
1108 KB |
Output is correct |
60 |
Correct |
25 ms |
980 KB |
Output is correct |
61 |
Correct |
39 ms |
1108 KB |
Output is correct |
62 |
Correct |
1241 ms |
7924 KB |
Output is correct |
63 |
Correct |
1167 ms |
7528 KB |
Output is correct |
64 |
Correct |
1150 ms |
7856 KB |
Output is correct |
65 |
Correct |
2069 ms |
31876 KB |
Output is correct |
66 |
Correct |
1559 ms |
36152 KB |
Output is correct |
67 |
Correct |
1376 ms |
36020 KB |
Output is correct |
68 |
Correct |
1124 ms |
35796 KB |
Output is correct |
69 |
Correct |
1288 ms |
35960 KB |
Output is correct |
70 |
Correct |
1135 ms |
36112 KB |
Output is correct |
71 |
Correct |
1243 ms |
36288 KB |
Output is correct |
72 |
Correct |
1209 ms |
36060 KB |
Output is correct |
73 |
Correct |
1203 ms |
36112 KB |
Output is correct |
74 |
Correct |
1204 ms |
36112 KB |
Output is correct |
75 |
Correct |
1341 ms |
36068 KB |
Output is correct |
76 |
Correct |
65 ms |
4684 KB |
Output is correct |
77 |
Correct |
98 ms |
4396 KB |
Output is correct |
78 |
Correct |
141 ms |
4808 KB |
Output is correct |
79 |
Correct |
400 ms |
34948 KB |
Output is correct |
80 |
Correct |
355 ms |
34968 KB |
Output is correct |
81 |
Correct |
383 ms |
34964 KB |
Output is correct |
82 |
Correct |
219 ms |
34892 KB |
Output is correct |
83 |
Correct |
222 ms |
34976 KB |
Output is correct |
84 |
Correct |
223 ms |
34696 KB |
Output is correct |
85 |
Correct |
285 ms |
34876 KB |
Output is correct |
86 |
Correct |
385 ms |
34904 KB |
Output is correct |
87 |
Correct |
315 ms |
34940 KB |
Output is correct |
88 |
Incorrect |
58 ms |
4428 KB |
Output isn't correct |
89 |
Halted |
0 ms |
0 KB |
- |