#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const ll N = (1 << 19) ;
ll n, d, cnt, a[N + 1], dp[N + 1], mx[2 * N + 1] ;
set<ll> s ;
map<ll, ll> mp ;
void update(ll l, ll r, ll ind, ll num, ll v)
{
if(l > ind || r < ind)
return ;
if(l == r)
{
mx[v] = num ;
return ;
}
ll 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]) ;
}
ll get_max(ll l, ll r,ll l1, ll r1, ll v)
{
if(l > r1 || r < l1)
return 0 ;
if(l1 <= l && r <= r1)
return mx[v] ;
ll 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(ll i = 1 ; i <= n ; i++)
{
cin >> a[i] ;
s.insert(a[i]) ;
}
for(ll i : s)
{
cnt++ ;
mp[i] = cnt ;
}
for(ll i = 1 ; i <= n ; i++)
a[i] = mp[a[i]] ;
if(n <= 7000)
{
ll ans = 0 ;
for(ll i = n ; i >= 1 ; i--)
{
ll mx = 0, ls = i, now = a[i] ;
pair<ll, ll> mn = {1e9, 1e9} ;
for(ll j = i + 1 ; j <= n ; j++)
{
if((j - ls) == d + 1)
{
ls = mn.se ;
now = max(now, mn.fi) ;
mn = {1e9, 1e9} ;
}
mn = min(mn, {a[j], j}) ;
if(a[j] > now)
mx = max(mx, dp[j]) ;
}
dp[i] = mx + 1 ;
ans = max(ans, dp[i]) ;
}
cout << ans ;
return 0 ;
}
if(n <= 20)
{
ll ans = 0 ;
for(ll i = 0 ; i < (1 << n) ; i++)
{
ll now = 0, mx = -1, ls = 1e9 ;
for(ll j = 0 ; j < n ; j++)
if(j - ls <= d && ((1 << j) & i))
{
ls = j ;
if(mx < a[j + 1])
now++ ;
mx = max(mx, a[j + 1]) ;
}
ans = max(ans, now) ;
}
cout << ans ;
return 0 ;
}
if(d == 1)
{
ll ans = 0 ;
for(ll i = 1 ; i <= n ; i++)
update(1, N, i, a[i], 1) ;
for(ll i = n ; i >= 1 ; i--)
{
ll l = i, r = n + 1 ;
while(l + 1 < r)
{
ll 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)
{
ll ans = 0 ;
for(ll i = 1 ; i <= n ; i++)
{
ll 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 |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
360 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
384 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 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 |
0 ms |
212 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
360 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
384 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 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 |
0 ms |
212 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
0 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
360 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
384 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 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 |
0 ms |
212 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
0 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1269 ms |
9656 KB |
Output is correct |
2 |
Correct |
1098 ms |
9748 KB |
Output is correct |
3 |
Correct |
1008 ms |
9680 KB |
Output is correct |
4 |
Correct |
1377 ms |
37720 KB |
Output is correct |
5 |
Correct |
1214 ms |
42552 KB |
Output is correct |
6 |
Correct |
1355 ms |
42608 KB |
Output is correct |
7 |
Correct |
1335 ms |
42392 KB |
Output is correct |
8 |
Correct |
1261 ms |
42484 KB |
Output is correct |
9 |
Correct |
1088 ms |
42524 KB |
Output is correct |
10 |
Correct |
1181 ms |
42588 KB |
Output is correct |
11 |
Correct |
1161 ms |
42632 KB |
Output is correct |
12 |
Correct |
1180 ms |
42520 KB |
Output is correct |
13 |
Correct |
1226 ms |
42516 KB |
Output is correct |
14 |
Correct |
1426 ms |
42576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
55 ms |
2668 KB |
Output is correct |
2 |
Correct |
98 ms |
2720 KB |
Output is correct |
3 |
Correct |
145 ms |
3300 KB |
Output is correct |
4 |
Correct |
493 ms |
41656 KB |
Output is correct |
5 |
Correct |
433 ms |
41724 KB |
Output is correct |
6 |
Correct |
501 ms |
41764 KB |
Output is correct |
7 |
Correct |
237 ms |
41896 KB |
Output is correct |
8 |
Correct |
250 ms |
41768 KB |
Output is correct |
9 |
Correct |
251 ms |
41376 KB |
Output is correct |
10 |
Correct |
308 ms |
41596 KB |
Output is correct |
11 |
Correct |
438 ms |
41768 KB |
Output is correct |
12 |
Correct |
413 ms |
41764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
360 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
384 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 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 |
0 ms |
212 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
0 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
29 |
Halted |
0 ms |
0 KB |
- |