#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define f first
#define s second
#define pii pair<int,int>
#define is insert
const long long INF = 10000000000;
const long long MOD = 1000000007;
//store test cases here
/*
*/
int n,x;
long long a[200001];
vector<long long> d;
vector<long long> r;
int f[200001];
int b[200001];
int bsearch(int a) {
int lo = 0;
int hi = n-1;
while (lo != hi) {
int mid = (lo+hi)/2;
if (r[mid] < a) {
hi = mid;
} else {
lo = mid+1;
}
//cout << lo << "\n";
}
return lo;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> x;
for (int i = 0; i < n; i++) {
cin >> a[i];
d.pb(INF);
r.pb(-1*INF);
}
d.pb(INF);
d[0] = -1*INF;
r.pb(-1*INF);
r[0] = INF;
for (int i = 0; i < n; i++) {
int ind = lower_bound(d.begin(),d.end(),a[i]+1) - d.begin();
if (d[ind-1] < a[i] && a[i] < d[ind]) {
d[ind] = a[i];
f[i] = ind;
} else {
f[i] = 1;
}
//cout << "i: " << i << " val: " << f[i] << "\n";
}
for (int i = n-1; i > -1; i--) {
int ind = bsearch(a[i]-1);
if (r[ind] < a[i] && a[i] <= r[ind-1]) {
r[ind] = a[i];
b[i] = ind;
} else {
b[i] = 1;
}
//cout << "i: " << i << " val: " << b[i] << "\n";
}
int ans = 0;
for (int i = 0; i <= n; i++) {
if (d[i] < INF) {
ans = i;
}
}
for (int i = n-1; i > 0; i--) {
if (a[i] <= a[i-1] && a[i-1] - a[i] < x) {
ans = max(ans,f[i-1] + b[i]);
}
}
cout << ans << "\n";
}
/* REMINDERS
* CHECK ARRAY BOUNDS, HOW BIG ARRAY HAS TO BE
* PLANNING!!!!!!!! Concrete plan before code
* IF CAN'T FIGURE ANYTHING OUT, MAKE TEN TEST CASES TO EVALUATE ALL TYPES OF SCENARIOS, THEN CONSTRUCT SOLUTION TO FIT IT
* IF CAN'T FIGURE ANYTHING OUT, MAKE TEN TEST CASES TO EVALUATE ALL TYPES OF SCENARIOS, THEN CONSTRUCT SOLUTION TO FIT IT
* IF CAN'T FIGURE ANYTHING OUT, MAKE TEN TEST CASES TO EVALUATE ALL TYPES OF SCENARIOS, THEN CONSTRUCT SOLUTION TO FIT IT
* NAIVE SOL FIRST TO CHECK AGAINST OPTIMIZED SOL
* MOD OUT EVERY STEP
* DON'T MAKE ASSUMPTIONS
* DON'T OVERCOMPLICATE
* CHECK INT VS LONG, IF YOU NEED TO STORE LARGE NUMBERS
* CHECK CONSTRAINTS, C <= N <= F...
* CHECK SPECIAL CASES, N = 1...
* TO TEST TLE/MLE, PLUG IN MAX VALS ALLOWED AND SEE WHAT HAPPENS
* ALSO CALCULATE BIG-O, OVERALL TIME COMPLEXITY
* IF ALL ELSE FAILS, DO CASEWORK
* compile with "g++ -std=c++11 filename.cpp" if using auto keyword
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
8912 KB |
Output is correct |
| 2 |
Correct |
61 ms |
8784 KB |
Output is correct |
| 3 |
Correct |
61 ms |
8792 KB |
Output is correct |
| 4 |
Correct |
60 ms |
8788 KB |
Output is correct |
| 5 |
Correct |
47 ms |
8004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
2676 KB |
Output is correct |
| 2 |
Correct |
15 ms |
2668 KB |
Output is correct |
| 3 |
Correct |
15 ms |
2676 KB |
Output is correct |
| 4 |
Incorrect |
12 ms |
2548 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
4708 KB |
Output is correct |
| 2 |
Incorrect |
37 ms |
4704 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
