#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];
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;
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;
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:84:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
84 | main() {
| ^~~~
Main.cpp: In function 'int main()':
Main.cpp:92:12: warning: unused variable 'm' [-Wunused-variable]
92 | int n, m, d;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
1 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 |
212 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 |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
1 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 |
212 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 |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
1 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 |
212 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 |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
194 ms |
2620 KB |
Output is correct |
2 |
Correct |
174 ms |
2628 KB |
Output is correct |
3 |
Correct |
244 ms |
3072 KB |
Output is correct |
4 |
Correct |
1666 ms |
821408 KB |
Output is correct |
5 |
Correct |
1296 ms |
955436 KB |
Output is correct |
6 |
Correct |
1622 ms |
955416 KB |
Output is correct |
7 |
Correct |
944 ms |
967404 KB |
Output is correct |
8 |
Correct |
923 ms |
971768 KB |
Output is correct |
9 |
Correct |
984 ms |
960404 KB |
Output is correct |
10 |
Correct |
920 ms |
958792 KB |
Output is correct |
11 |
Correct |
1481 ms |
955216 KB |
Output is correct |
12 |
Correct |
1294 ms |
955276 KB |
Output is correct |
13 |
Correct |
1375 ms |
955452 KB |
Output is correct |
14 |
Correct |
1474 ms |
955448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
109 ms |
5068 KB |
Output is correct |
2 |
Correct |
164 ms |
5520 KB |
Output is correct |
3 |
Correct |
316 ms |
16624 KB |
Output is correct |
4 |
Correct |
1359 ms |
955492 KB |
Output is correct |
5 |
Correct |
1213 ms |
955396 KB |
Output is correct |
6 |
Correct |
1358 ms |
954788 KB |
Output is correct |
7 |
Correct |
809 ms |
973784 KB |
Output is correct |
8 |
Correct |
1191 ms |
975000 KB |
Output is correct |
9 |
Correct |
856 ms |
949440 KB |
Output is correct |
10 |
Correct |
1031 ms |
952344 KB |
Output is correct |
11 |
Correct |
1597 ms |
955444 KB |
Output is correct |
12 |
Correct |
1390 ms |
955356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
1 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 |
212 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 |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |