#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()
int a[(int) 3e5 + 10];
struct SegmentTree {
vector<ll> sgt;
SegmentTree(int n) {
sgt.resize(n, LLONG_MAX);
}
ll get(int k, int l, int r, ll v) {
if (l == r) return l;
int m = (l + r) / 2;
if (sgt[k * 2 + 1] < v) return get(k * 2 + 1, m + 1, r, v);
return get(k * 2, l, m, v);
}
void update(int k, int l, int r, int i, ll v) {
if (l > i || r < i) return;
if (l == r) {
sgt[k] = v;
return;
}
int m = (l + r) / 2;
update(k * 2, l, m, i, v);
update(k * 2 + 1, m + 1, r, i, v);
sgt[k] = min(sgt[k * 2], sgt[k * 2 + 1]);
}
} sgt(4 * (3e5 + 10));
int main() {
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
int n, d;
cin >> n >> d;
for (int i = 1; i <= n; i++) cin >> a[i];
ll ans = 0;
multiset<ll> lis[n + 10];
lis[0].insert(0);
sgt.update(1, 0, n, 0, 0);
ll dp[n + 10];
dp[0] = 0;
for (int i = 1; i <= n; i++) {
ll mn;
if (i > d + 1) {
mn = *lis[dp[i - d - 1]].begin();
lis[dp[i - d - 1]].erase(lis[dp[i - d - 1]].find(a[i - d - 1]));
if (lis[dp[i - d - 1]].size()) {
if (*lis[dp[i - d - 1]].begin() != mn) sgt.update(1, 0, n, i - d - 1, *lis[dp[i - d - 1]].begin());
}
else sgt.update(1, 0, n, i - d - 1, LLONG_MAX);
}
dp[i] = sgt.get(1, 0, n, a[i]) + 1;
if (lis[dp[i]].size()) mn = *lis[dp[i]].begin();
lis[dp[i]].insert(a[i]);
if (lis[dp[i]].size() == 1 || mn != *lis[dp[i]].begin()) sgt.update(1, 0, n, dp[i], a[i]);
ans = max(ans, dp[i]);
// cout << i << " : " << dp[i] << endl;
}
cout << ans;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:63:36: warning: 'mn' may be used uninitialized in this function [-Wmaybe-uninitialized]
63 | if (lis[dp[i]].size() == 1 || mn != *lis[dp[i]].begin()) sgt.update(1, 0, n, dp[i], a[i]);
| ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
9820 KB |
Output is correct |
2 |
Correct |
2 ms |
9820 KB |
Output is correct |
3 |
Correct |
2 ms |
9816 KB |
Output is correct |
4 |
Correct |
2 ms |
9820 KB |
Output is correct |
5 |
Correct |
2 ms |
9820 KB |
Output is correct |
6 |
Correct |
2 ms |
9820 KB |
Output is correct |
7 |
Correct |
2 ms |
9848 KB |
Output is correct |
8 |
Correct |
2 ms |
9820 KB |
Output is correct |
9 |
Correct |
2 ms |
9820 KB |
Output is correct |
10 |
Correct |
2 ms |
9816 KB |
Output is correct |
11 |
Correct |
3 ms |
9816 KB |
Output is correct |
12 |
Correct |
2 ms |
9820 KB |
Output is correct |
13 |
Correct |
3 ms |
9852 KB |
Output is correct |
14 |
Correct |
2 ms |
9820 KB |
Output is correct |
15 |
Correct |
2 ms |
9820 KB |
Output is correct |
16 |
Correct |
2 ms |
9820 KB |
Output is correct |
17 |
Correct |
2 ms |
9820 KB |
Output is correct |
18 |
Correct |
2 ms |
9820 KB |
Output is correct |
19 |
Correct |
2 ms |
9820 KB |
Output is correct |
20 |
Correct |
2 ms |
9820 KB |
Output is correct |
21 |
Incorrect |
2 ms |
9856 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
9820 KB |
Output is correct |
2 |
Correct |
2 ms |
9820 KB |
Output is correct |
3 |
Correct |
2 ms |
9816 KB |
Output is correct |
4 |
Correct |
2 ms |
9820 KB |
Output is correct |
5 |
Correct |
2 ms |
9820 KB |
Output is correct |
6 |
Correct |
2 ms |
9820 KB |
Output is correct |
7 |
Correct |
2 ms |
9848 KB |
Output is correct |
8 |
Correct |
2 ms |
9820 KB |
Output is correct |
9 |
Correct |
2 ms |
9820 KB |
Output is correct |
10 |
Correct |
2 ms |
9816 KB |
Output is correct |
11 |
Correct |
3 ms |
9816 KB |
Output is correct |
12 |
Correct |
2 ms |
9820 KB |
Output is correct |
13 |
Correct |
3 ms |
9852 KB |
Output is correct |
14 |
Correct |
2 ms |
9820 KB |
Output is correct |
15 |
Correct |
2 ms |
9820 KB |
Output is correct |
16 |
Correct |
2 ms |
9820 KB |
Output is correct |
17 |
Correct |
2 ms |
9820 KB |
Output is correct |
18 |
Correct |
2 ms |
9820 KB |
Output is correct |
19 |
Correct |
2 ms |
9820 KB |
Output is correct |
20 |
Correct |
2 ms |
9820 KB |
Output is correct |
21 |
Incorrect |
2 ms |
9856 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
9820 KB |
Output is correct |
2 |
Correct |
2 ms |
9820 KB |
Output is correct |
3 |
Correct |
2 ms |
9816 KB |
Output is correct |
4 |
Correct |
2 ms |
9820 KB |
Output is correct |
5 |
Correct |
2 ms |
9820 KB |
Output is correct |
6 |
Correct |
2 ms |
9820 KB |
Output is correct |
7 |
Correct |
2 ms |
9848 KB |
Output is correct |
8 |
Correct |
2 ms |
9820 KB |
Output is correct |
9 |
Correct |
2 ms |
9820 KB |
Output is correct |
10 |
Correct |
2 ms |
9816 KB |
Output is correct |
11 |
Correct |
3 ms |
9816 KB |
Output is correct |
12 |
Correct |
2 ms |
9820 KB |
Output is correct |
13 |
Correct |
3 ms |
9852 KB |
Output is correct |
14 |
Correct |
2 ms |
9820 KB |
Output is correct |
15 |
Correct |
2 ms |
9820 KB |
Output is correct |
16 |
Correct |
2 ms |
9820 KB |
Output is correct |
17 |
Correct |
2 ms |
9820 KB |
Output is correct |
18 |
Correct |
2 ms |
9820 KB |
Output is correct |
19 |
Correct |
2 ms |
9820 KB |
Output is correct |
20 |
Correct |
2 ms |
9820 KB |
Output is correct |
21 |
Incorrect |
2 ms |
9856 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
111 ms |
30156 KB |
Output is correct |
2 |
Correct |
174 ms |
29988 KB |
Output is correct |
3 |
Incorrect |
170 ms |
30276 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
183 ms |
44656 KB |
Output is correct |
2 |
Correct |
171 ms |
44372 KB |
Output is correct |
3 |
Correct |
215 ms |
44380 KB |
Output is correct |
4 |
Correct |
214 ms |
44188 KB |
Output is correct |
5 |
Correct |
203 ms |
44360 KB |
Output is correct |
6 |
Correct |
197 ms |
44368 KB |
Output is correct |
7 |
Correct |
148 ms |
44192 KB |
Output is correct |
8 |
Correct |
233 ms |
44368 KB |
Output is correct |
9 |
Correct |
152 ms |
44240 KB |
Output is correct |
10 |
Correct |
176 ms |
44284 KB |
Output is correct |
11 |
Correct |
244 ms |
44368 KB |
Output is correct |
12 |
Correct |
152 ms |
44328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
9820 KB |
Output is correct |
2 |
Correct |
2 ms |
9820 KB |
Output is correct |
3 |
Correct |
2 ms |
9816 KB |
Output is correct |
4 |
Correct |
2 ms |
9820 KB |
Output is correct |
5 |
Correct |
2 ms |
9820 KB |
Output is correct |
6 |
Correct |
2 ms |
9820 KB |
Output is correct |
7 |
Correct |
2 ms |
9848 KB |
Output is correct |
8 |
Correct |
2 ms |
9820 KB |
Output is correct |
9 |
Correct |
2 ms |
9820 KB |
Output is correct |
10 |
Correct |
2 ms |
9816 KB |
Output is correct |
11 |
Correct |
3 ms |
9816 KB |
Output is correct |
12 |
Correct |
2 ms |
9820 KB |
Output is correct |
13 |
Correct |
3 ms |
9852 KB |
Output is correct |
14 |
Correct |
2 ms |
9820 KB |
Output is correct |
15 |
Correct |
2 ms |
9820 KB |
Output is correct |
16 |
Correct |
2 ms |
9820 KB |
Output is correct |
17 |
Correct |
2 ms |
9820 KB |
Output is correct |
18 |
Correct |
2 ms |
9820 KB |
Output is correct |
19 |
Correct |
2 ms |
9820 KB |
Output is correct |
20 |
Correct |
2 ms |
9820 KB |
Output is correct |
21 |
Incorrect |
2 ms |
9856 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |