#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long int
#define ld long double
using namespace std;
const int N = 1e6 + 5;
const int MOD = 1e9 + 7;
int main(){
fast;
int n, x;
cin >> n >> x;
int a[n];
for(int i = 0; i < n; ++i)
cin >> a[i];
vector<pair<int, int> > lis;
lis.push_back({a[0], 0});
for(int i = 1; i < n; ++i){
if(a[i] > lis.back().first){
lis.push_back({a[i], i});
continue;
}
int low = 0, high = lis.size() - 1, ans = -1;
while(low <= high){
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};
}
int mx = lis.size();
for(auto k : lis)
a[k.second] += x;
vector<int> lis1;
lis1.push_back(a[0]);
for(int i = 1; i < n; ++i){
if(a[i] > lis1.back()){
lis1.push_back(a[i]);
continue;
}
int low = 0, high = lis1.size() - 1, ans = -1;
while(low <= high){
int mid = (low + high) / 2;
if(lis1[mid] >= a[i]){
ans = mid;
high = mid - 1;
}
else
low = mid + 1;
}
if(ans == -1)
continue;
lis1[ans] = a[i];
}
mx = max(mx, (int) lis1.size());
for(auto k : lis)
a[k.second] -= 2*x;
lis1.clear();
lis1.push_back(a[0]);
for(int i = 1; i < n; ++i){
if(a[i] > lis1.back()){
lis1.push_back(a[i]);
continue;
}
int low = 0, high = lis1.size() - 1, ans = -1;
while(low <= high){
int mid = (low + high) / 2;
if(lis1[mid] >= a[i]){
ans = mid;
high = mid - 1;
}
else
low = mid + 1;
}
if(ans == -1)
continue;
lis1[ans] = a[i];
}
cout << max(mx, (int) lis1.size()) << '\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
64 ms |
3092 KB |
Output is correct |
2 |
Correct |
63 ms |
3180 KB |
Output is correct |
3 |
Correct |
65 ms |
3220 KB |
Output is correct |
4 |
Correct |
61 ms |
3008 KB |
Output is correct |
5 |
Correct |
31 ms |
4072 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
1004 KB |
Output is correct |
2 |
Correct |
15 ms |
1004 KB |
Output is correct |
3 |
Correct |
16 ms |
1004 KB |
Output is correct |
4 |
Incorrect |
8 ms |
1264 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
30 ms |
1772 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |