#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()
typedef pair<int, pi> pii;
const int maxn = 200010;
const int INF = LLONG_MAX/2;
const int mod = 1e9+7;
int n, X;
struct node {
int s,m,e,v;
node *l, *r;
node (int _s, int _e) {
s = _s; e = _e; m = (s+e)/2;
v = 0;
if (s != e) {
l = new node(s,m);
r = new node(m+1,e);
}
}
void up(int x, int newv) {
if (s == e) v = max(v,newv);
else {
if (x <= m) l -> up(x,newv);
else r -> up(x,newv);
v = max(l -> v, r -> v);
}
}
int rmq(int x, int y) {
if (x == s and e == y) return v;
if (x > m) return r -> rmq(x,y);
else if (y <= m) return l -> rmq(x,y);
else return max(l -> rmq(x,m), r -> rmq(m+1,y));
}
}*root;
int best[maxn];
int suf;
int32_t main() {
//FAST
cin >> n >> X;
vector <int> v(n);
for (int i =0;i<n;i++) {
cin >> v[i];
}
vector <int> vv = v;
sort(all(vv));
root = new node(0,n-1);
vector <int> lis;
for (int i =0;i<n;i++) {
int x = v[i];
if (lis.empty() or x > lis.back()) {
lis.push_back(x);
best[i] = lis.size();
} else {
int pos = lower_bound(all(lis),x) - lis.begin();
lis[pos] = x;
best[i] = pos + 1;
}
}
//cout << "HELLO";
//for (int i =0;i<n;i++) cout << best[i] << " ";
int rans = best[n-1];
for (int i =n-1;i>=0;i--) {
int p = upper_bound(all(vv),v[i] - X) - vv.begin();
if (p <= n-1) suf = root -> rmq(p,n-1);
else suf = 0;
rans = max(rans, best[i] + suf);
p = lower_bound(all(vv),v[i]) - vv.begin();
if (p <= n-1) suf = root -> rmq(p,n-1);
else suf = 0;
root -> up(p,suf+1);
}
cout << rans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
423 ms |
32108 KB |
Output is correct |
2 |
Correct |
445 ms |
31980 KB |
Output is correct |
3 |
Correct |
404 ms |
31980 KB |
Output is correct |
4 |
Correct |
414 ms |
31980 KB |
Output is correct |
5 |
Incorrect |
178 ms |
32096 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
80 ms |
8428 KB |
Output is correct |
2 |
Correct |
85 ms |
8300 KB |
Output is correct |
3 |
Correct |
83 ms |
8428 KB |
Output is correct |
4 |
Incorrect |
40 ms |
8424 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
163 ms |
16364 KB |
Output is correct |
2 |
Correct |
159 ms |
16236 KB |
Output is correct |
3 |
Correct |
356 ms |
32108 KB |
Output is correct |
4 |
Incorrect |
155 ms |
32096 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |