#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
const int MAX = 4e5 + 10;
int n, k;
int x, y;
int ucit[MAX];
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() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> ucit[i];
v.push_back(ucit[i]);
v.push_back(ucit[i] + k);
}
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[ucit[i]];
}
for (int i = n; i >= 1; i--) {
x = arr[i];
dpBack[i] = queryBack(0, 2 * n - 1, x + 1, 1) + 1;
updateBack(0, 2 * n - 1, x, 1, dpBack[i]);
}
cout << treeBack[1] << "\n";
return 0;
int sol = queryBack(0, 2 * n - 1, -1, 1);
for (int i = 1; i < n; i++) {
x = arr[i];
dpFront[i] = queryFront(0, 2 * n - 1, x - 1, 1) + 1;
updateFront(0, 2 * n - 1, x, 1, dpFront[i]);
sol = max(sol, queryFront(0, 2 * n - 1, mp[ucit[i + 1] + k] - 1 , 1) + dpBack[i + 1]);
}
cout << sol << "\n";
return 0;
}
Compilation message
glo.cpp: In function 'int main()':
glo.cpp:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for (int i = 1; i < v.size(); i++) {
| ~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
347 ms |
15608 KB |
Output is correct |
2 |
Correct |
353 ms |
15652 KB |
Output is correct |
3 |
Correct |
327 ms |
15796 KB |
Output is correct |
4 |
Correct |
318 ms |
15752 KB |
Output is correct |
5 |
Correct |
146 ms |
9972 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
76 ms |
6988 KB |
Output is correct |
2 |
Correct |
77 ms |
6948 KB |
Output is correct |
3 |
Correct |
93 ms |
6968 KB |
Output is correct |
4 |
Incorrect |
45 ms |
4164 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
156 ms |
12688 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |