#ifdef Home
#define _GLIBCXX_DEBUG
#endif // Home
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 300300;
int dp[N], arr[N], L[N];
struct SlideWin{
stack < int > L, R, S;
void add(int x) {
R.push(max(R.empty() ? 0 : R.top(), x));
S.push(x);
}
void del() {
if(L.empty()) {
for(; !S.empty();) {
L.push(max(L.empty() ? 0 : L.top(), S.top()));
S.pop();
R.pop();
}
}
L.pop();
}
int get_max() {
return max(L.empty() ? 0 : L.top(),
R.empty() ? 0 : R.top());
}
};
map < int, SlideWin > mp;
int lg2(int x) {
return 31 - __builtin_clz(x);
}
struct node{
int l, r, mx = 0;
node *left = NULL, *right = NULL;
node(int _l, int _r):l(_l), r(_r) {};
};
void check(node *x) {
if(x->left == NULL) {
x->left = new node(x->l, (x->l + x->r) / 2);
}
if(x->right == NULL) {
x->right = new node((x->l + x->r) / 2, x->r);
}
}
void update(int pos, node *x) {
if(x->l + 1 == x->r) {
x->mx = mp[x->l].get_max();
return;
}
check(x);
pos < x->left->r ?
update(pos, x->left) :
update(pos, x->right) ;
x->mx = max(x->left->mx, x->right->mx);
}
int get(int r, node *x) {
if(x->r <= r || x->mx == 0) {
return x->mx;
}
check(x);
int res = get(r, x->left);
if(x->right->l < r) {
res = max(res, get(r, x->right));
}
return res;
}
main() {
#ifdef Home
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // Home
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, d;
cin >> n >> d;
if(n < 21) {
for(int i = 0; i < n; ++ i) {
cin >> arr[i];
}
int ans = 0;
for(int msk = (1<<n); msk --> 0;) {
int k = 0, tmp = msk, pr = -1, cr, mx = -1;
for(; tmp; tmp -= (-tmp&tmp)) {
cr = lg2(-tmp&tmp);
if(pr != -1 && cr - pr > d) {
k = 0;
break;
}
if(mx < arr[cr]) {
++ k;
mx = arr[cr];
}
pr = cr;
}
if(pr == n - 1) {
ans = max(ans, k);
}
}
cout << ans;
return 0;
}
stack < int > st;
node *root = new node(0, (1<<30));
for(int i = 1; i <= n; ++ i) {
cin >> arr[i];
if(i > d + 1) {
mp[arr[i - d - 1]].del();
update(arr[i - d - 1], root);
}
dp[i] = get(arr[i], root) + 1;
for(; !st.empty() && arr[st.top()] <= arr[i]; st.pop()) {
dp[i] = max(dp[i], dp[st.top()] + (arr[st.top()] < arr[i]));
}
st.push(i);
mp[arr[i]].add(dp[i]);
update(arr[i], root);
}
int mx = 0;
for(; !st.empty(); st.pop()) {
mx = max(mx, dp[st.top()]);
}
cout << mx;
}
Compilation message
Main.cpp:88:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
88 | main() {
| ^~~~
Main.cpp: In function 'int main()':
Main.cpp:96:12: warning: unused variable 'm' [-Wunused-variable]
96 | int n, m, d;
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
4 ms |
212 KB |
Output is correct |
16 |
Correct |
2 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
27 ms |
212 KB |
Output is correct |
19 |
Correct |
6 ms |
328 KB |
Output is correct |
20 |
Correct |
25 ms |
332 KB |
Output is correct |
21 |
Correct |
13 ms |
332 KB |
Output is correct |
22 |
Correct |
24 ms |
336 KB |
Output is correct |
23 |
Correct |
8 ms |
328 KB |
Output is correct |
24 |
Correct |
8 ms |
212 KB |
Output is correct |
25 |
Correct |
2 ms |
212 KB |
Output is correct |
26 |
Correct |
3 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
4 ms |
212 KB |
Output is correct |
16 |
Correct |
2 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
27 ms |
212 KB |
Output is correct |
19 |
Correct |
6 ms |
328 KB |
Output is correct |
20 |
Correct |
25 ms |
332 KB |
Output is correct |
21 |
Correct |
13 ms |
332 KB |
Output is correct |
22 |
Correct |
24 ms |
336 KB |
Output is correct |
23 |
Correct |
8 ms |
328 KB |
Output is correct |
24 |
Correct |
8 ms |
212 KB |
Output is correct |
25 |
Correct |
2 ms |
212 KB |
Output is correct |
26 |
Correct |
3 ms |
212 KB |
Output is correct |
27 |
Correct |
2 ms |
1876 KB |
Output is correct |
28 |
Incorrect |
2 ms |
1924 KB |
Output isn't correct |
29 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
4 ms |
212 KB |
Output is correct |
16 |
Correct |
2 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
27 ms |
212 KB |
Output is correct |
19 |
Correct |
6 ms |
328 KB |
Output is correct |
20 |
Correct |
25 ms |
332 KB |
Output is correct |
21 |
Correct |
13 ms |
332 KB |
Output is correct |
22 |
Correct |
24 ms |
336 KB |
Output is correct |
23 |
Correct |
8 ms |
328 KB |
Output is correct |
24 |
Correct |
8 ms |
212 KB |
Output is correct |
25 |
Correct |
2 ms |
212 KB |
Output is correct |
26 |
Correct |
3 ms |
212 KB |
Output is correct |
27 |
Correct |
2 ms |
1876 KB |
Output is correct |
28 |
Incorrect |
2 ms |
1924 KB |
Output isn't correct |
29 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
184 ms |
2616 KB |
Output is correct |
2 |
Correct |
162 ms |
2620 KB |
Output is correct |
3 |
Correct |
223 ms |
3108 KB |
Output is correct |
4 |
Correct |
1424 ms |
821532 KB |
Output is correct |
5 |
Correct |
1242 ms |
955516 KB |
Output is correct |
6 |
Correct |
1555 ms |
955420 KB |
Output is correct |
7 |
Correct |
908 ms |
967404 KB |
Output is correct |
8 |
Correct |
901 ms |
971952 KB |
Output is correct |
9 |
Correct |
926 ms |
960288 KB |
Output is correct |
10 |
Correct |
908 ms |
958796 KB |
Output is correct |
11 |
Correct |
1124 ms |
955332 KB |
Output is correct |
12 |
Correct |
1249 ms |
955412 KB |
Output is correct |
13 |
Correct |
1354 ms |
955364 KB |
Output is correct |
14 |
Correct |
1474 ms |
955452 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
112 ms |
5124 KB |
Output is correct |
2 |
Correct |
170 ms |
5576 KB |
Output is correct |
3 |
Correct |
346 ms |
16632 KB |
Output is correct |
4 |
Correct |
1907 ms |
955452 KB |
Output is correct |
5 |
Correct |
1218 ms |
955316 KB |
Output is correct |
6 |
Correct |
1413 ms |
954836 KB |
Output is correct |
7 |
Correct |
808 ms |
973880 KB |
Output is correct |
8 |
Correct |
811 ms |
975080 KB |
Output is correct |
9 |
Correct |
815 ms |
949524 KB |
Output is correct |
10 |
Correct |
994 ms |
952348 KB |
Output is correct |
11 |
Correct |
1344 ms |
955444 KB |
Output is correct |
12 |
Correct |
1248 ms |
955340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
4 ms |
212 KB |
Output is correct |
16 |
Correct |
2 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
27 ms |
212 KB |
Output is correct |
19 |
Correct |
6 ms |
328 KB |
Output is correct |
20 |
Correct |
25 ms |
332 KB |
Output is correct |
21 |
Correct |
13 ms |
332 KB |
Output is correct |
22 |
Correct |
24 ms |
336 KB |
Output is correct |
23 |
Correct |
8 ms |
328 KB |
Output is correct |
24 |
Correct |
8 ms |
212 KB |
Output is correct |
25 |
Correct |
2 ms |
212 KB |
Output is correct |
26 |
Correct |
3 ms |
212 KB |
Output is correct |
27 |
Correct |
2 ms |
1876 KB |
Output is correct |
28 |
Incorrect |
2 ms |
1924 KB |
Output isn't correct |
29 |
Halted |
0 ms |
0 KB |
- |