#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const ll inf = (ll)1e10;
const int N = (int)2e5 + 10;
vector<pii> qq[N];
int main(){
fastIO;
int n;
ll x;
cin >> n >> x;
vector<ll> v(n);
for(int i = 0 ; i < n; i ++ ){
cin >> v[i];
}
vector<ll> q;
ll c;
int id;
int res = 0;
for(int i = 0 ; i < n; i ++ ){
c = v[i] - x;
id = lower_bound(q.begin(), q.end(), c) - q.begin();
if(id == q.size()){
q.push_back(c);
}
else{
q[id] = c;
}
qq[i+1].push_back(mp(c, id+1));
res = max(res, id + 1);
}
vector<ll> g = {};
int l, r, mid;
for(int i = n - 1; i >= 0; i -- ){
l = 0, r = g.size()+1;
while(l + 1 < r){
mid = (l + r) / 2;
if(g[mid] < v[i]){
r = mid;
}
else{
l = mid;
}
}
if(l == g.size()){
g.push_back(v[i]);
}
else{
g[l] = v[i];
}
for(auto x : qq[i]){
l = 0, r = g.size();
while(l + 1 < r){
mid = (l + r) / 2;
if(g[mid] > x.fi)
l = mid;
else
r = mid;
}
res = max(res, l + (g[l]>x.fi) + x.se);
}
}
cout << res << "\n";
return 0;
}
Compilation message
glo.cpp: In function 'int main()':
glo.cpp:33:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | if(id == q.size()){
| ~~~^~~~~~~~~~~
glo.cpp:55:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | if(l == g.size()){
| ~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4992 KB |
Output is correct |
2 |
Incorrect |
4 ms |
4992 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4992 KB |
Output is correct |
2 |
Incorrect |
4 ms |
4992 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4992 KB |
Output is correct |
2 |
Incorrect |
4 ms |
4992 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
12920 KB |
Output is correct |
2 |
Correct |
51 ms |
12920 KB |
Output is correct |
3 |
Correct |
51 ms |
12920 KB |
Output is correct |
4 |
Correct |
52 ms |
12920 KB |
Output is correct |
5 |
Correct |
40 ms |
13680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
7040 KB |
Output is correct |
2 |
Correct |
15 ms |
7040 KB |
Output is correct |
3 |
Correct |
16 ms |
7040 KB |
Output is correct |
4 |
Incorrect |
13 ms |
7164 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
27 ms |
8960 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4992 KB |
Output is correct |
2 |
Incorrect |
4 ms |
4992 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |