#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
using namespace std;
const long long int N = 1e6 + 5;
const long long int MOD = 1e9 + 7;
int main(){
fast;
long long int n, x;
cin >> n >> x;
long long int a[n];
for(long long int i = 0; i < n; ++i)
cin >> a[i];
vector<pair<long long int, long long int> > lis;
lis.push_back({a[0], 0});
for(long long int i = 1; i < n; ++i){
if(a[i] > lis.back().first){
lis.push_back({a[i], i});
continue;
}
long long int low = 0, high = lis.size() - 1, ans = -1;
while(low <= high){
long long int mid = (low + high) / 2;
if(lis[mid].first >= a[i]){
ans = mid;
high = mid - 1;
}
else
low = mid + 1;
}
if(ans == -1)
continue;
lis[ans] = {a[i], i};
}
if(x == 0){
cout << lis.size() << '\n';
return 0;
}
int mx = lis.size();
lis.push_back({0, 0});
lis.push_back({INT_MAX, n - 1});
sort(lis.begin(), lis.end());
for(int i = 1; i < lis.size(); ++i){
int r = lis[i].second, l = lis[i - 1].second;
for(int j = l; j <= r; ++j)
a[j] += x;
vector<long long int> lis1;
lis1.push_back(a[0]);
for(int j = 1; j < n; ++j){
if(a[j] > lis1.back()){
lis1.push_back(a[j]);
continue;
}
int low = 0, ans = -1, high = lis1.size();
while(low <= high){
int mid = (low + high) / 2;
if(lis1[mid] >= a[j]){
ans = mid;
high = mid - 1;
}
else
low = mid + 1;
}
if(ans == -1) continue;
lis1[ans] = a[j];
}
mx = max(mx, (int) lis1.size());
for(int j = l; j <= r; ++j)
a[j] -= 2*x;
lis1.clear();
lis1.push_back(a[0]);
for(int j = 1; j < n; ++j){
if(a[j] > lis1.back()){
lis1.push_back(a[j]);
continue;
}
int low = 0, ans = -1, high = lis1.size();
while(low <= high){
int mid = (low + high) / 2;
if(lis1[mid] >= a[j]){
ans = mid;
high = mid - 1;
}
else
low = mid + 1;
}
if(ans == -1) continue;
lis1[ans] = a[j];
}
mx = max(mx, (int) lis1.size());
for(int j = l; j <= r; ++j)
a[j] += x;
}
cout << mx << '\n';
return 0;
}
Compilation message
glo.cpp: In function 'int main()':
glo.cpp:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i = 1; i < lis.size(); ++i){
| ~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
1900 KB |
Output is correct |
2 |
Correct |
35 ms |
1900 KB |
Output is correct |
3 |
Correct |
35 ms |
1900 KB |
Output is correct |
4 |
Correct |
36 ms |
1900 KB |
Output is correct |
5 |
Correct |
24 ms |
4072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2085 ms |
748 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2045 ms |
1132 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |