#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
const int MAX = 2e5 + 10;
int n, k;
int x, y;
int arr[MAX];
int treeFront[4 * MAX];
int treeBack[4 * MAX];
int dpFront[MAX];
int dpBack[MAX];
vector <int> v;
map <int, int> mp;
int id;
void updateFront(int left, int right, int a, int idx, int val) {
if (left > a || a > right) return;
if (left == right) {
treeFront[idx] = max(treeFront[idx], val);
return;
}
int mid = (left + right) / 2;
updateFront(left, mid, a, idx * 2, val);
updateFront(mid + 1, right, a, idx * 2 + 1, val);
treeFront[idx] = max(treeFront[idx * 2], treeFront[idx * 2 + 1]);
}
void updateBack(int left, int right, int a, int idx, int val) {
if (left > a || a > right) return;
if (left == right) {
treeBack[idx] = max(treeBack[idx], val);
return;
}
int mid = (left + right) / 2;
updateBack(left, mid, a, idx * 2, val);
updateBack(mid + 1, right, a, idx * 2 + 1, val);
treeBack[idx] = max(treeBack[idx * 2], treeBack[idx * 2 + 1]);
}
int queryFront(int left, int right, int a, int idx) {
if (left > a) return 0;
if (a >= right) {
return treeFront[idx];
}
int mid = (left + right) / 2;
int ret1 = queryFront(left, mid, a, idx * 2);
int ret2 = queryFront(mid + 1, right, a, idx * 2 + 1);
return max(ret1, ret2);
}
int queryBack(int left, int right, int a, int idx) {
if (right < a) return 0;
if (a <= left) {
return treeBack[idx];
}
int mid = (left + right) / 2;
int ret1 = queryBack(left, mid, a, idx * 2);
int ret2 = queryBack(mid + 1, right, a, idx * 2 + 1);
return max(ret1, ret2);
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
v.push_back(arr[i]);
}
sort(v.begin(), v.end());
mp[v[0]] = 0;
id = 1;
for (int i = 1; i < v.size(); i++) {
if (v[i] == v[i - 1]) continue;
mp[v[i]] = id;
id++;
}
for (int i = 1; i <= n; i++) {
arr[i] = mp[arr[i]];
}
for (int i = n; i >= 1; i--) {
x = arr[i];
dpBack[i] = queryBack(0, n - 1, x + 1, 1) + 1;
updateBack(0, n - 1, x, 1, dpBack[i]);
}
int sol = queryBack(0, n - 1, -1, 1);
for (int i = 1; i < n; i++) {
x = arr[i];
y = arr[i + 1];
dpFront[i] = queryFront(0, n - 1, x - 1, 1) + 1;
updateFront(0, n - 1, x, 1, dpFront[i]);
sol = max(sol, queryFront(0, n - 1, y - 1 + k, 1) + dpBack[i + 1]);
}
sol = max(sol, queryFront(0, n - 1, id, 1));
cout << sol << "\n";
return 0;
}
Compilation message
glo.cpp: In function 'int main()':
glo.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for (int i = 1; i < v.size(); i++) {
| ~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
300 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
300 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
499 ms |
18832 KB |
Output is correct |
2 |
Correct |
535 ms |
18920 KB |
Output is correct |
3 |
Correct |
527 ms |
18908 KB |
Output is correct |
4 |
Correct |
586 ms |
18824 KB |
Output is correct |
5 |
Correct |
275 ms |
11412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
102 ms |
4884 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
201 ms |
9544 KB |
Output is correct |
2 |
Correct |
255 ms |
9584 KB |
Output is correct |
3 |
Correct |
460 ms |
18916 KB |
Output is correct |
4 |
Correct |
244 ms |
11316 KB |
Output is correct |
5 |
Correct |
145 ms |
9184 KB |
Output is correct |
6 |
Correct |
311 ms |
17412 KB |
Output is correct |
7 |
Correct |
324 ms |
18136 KB |
Output is correct |
8 |
Correct |
206 ms |
9496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
300 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |