#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
vector<int> lis(vector<int> &arr, int constX) {
vector<int> dp(arr.size());
set<pii> s;
for (int i = 0; i < arr.size();i++) {
int v = arr[i];
if (constX > 0) {
auto it = s.lower_bound({v, 0});
if (s.empty()) dp[i] = 0;
else {
it = s.lower_bound({v + constX, 0});
bool remOld = false;
if (it == s.end()) {
it--;
}
else if (it != s.begin()) it--;
else remOld = true;
dp[i] = it->second - (remOld);
}
}
if (s.empty()) {
s.insert({v,1});
}
auto it = s.lower_bound({v,0});
bool remOld = true;
if (it == s.end()) {
it--;
remOld = false;
}
int p = it->second;
if (it->first > v || !remOld) {
if (remOld) s.erase(it);
s.emplace(v,p + (!remOld));
}
if (constX == 0)
dp[i] = p + !remOld;
}
return dp;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n, x; cin >> n >> x;
vector<int> arr(n), revArr(n);
for (int i = 0; i < n; ++i) {
cin >> arr[i];
revArr[i] = -arr[i];
}
std::reverse(revArr.begin(), revArr.end());
auto before = lis(arr,0), after = lis(revArr,x);
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = max(ans, before[i] + after[n - 1 - i]);
if (ans == 6) {
int stop = 25;
}
}
cout << ans;
return 0;
}
Compilation message
glo.cpp: In function 'std::vector<int> lis(std::vector<int>&, int)':
glo.cpp:9:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | for (int i = 0; i < arr.size();i++) {
| ~~^~~~~~~~~~~~
glo.cpp: In function 'int main()':
glo.cpp:65:17: warning: unused variable 'stop' [-Wunused-variable]
65 | int stop = 25;
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
67 ms |
3412 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
1112 KB |
Output is correct |
2 |
Correct |
18 ms |
1624 KB |
Output is correct |
3 |
Correct |
18 ms |
1556 KB |
Output is correct |
4 |
Correct |
16 ms |
2640 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
22 ms |
2652 KB |
Output is correct |
7 |
Correct |
14 ms |
1628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
1820 KB |
Output is correct |
2 |
Correct |
33 ms |
1880 KB |
Output is correct |
3 |
Correct |
88 ms |
5344 KB |
Output is correct |
4 |
Correct |
79 ms |
9300 KB |
Output is correct |
5 |
Correct |
45 ms |
4844 KB |
Output is correct |
6 |
Correct |
61 ms |
9040 KB |
Output is correct |
7 |
Correct |
71 ms |
9556 KB |
Output is correct |
8 |
Correct |
30 ms |
2908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |