This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
# define int long long
# define fir first
# define sec second
# define pb push_back
# define endl "\n"
const int cnst = 2e5+5;
bool mutipletestcase = 0;
//bool debug = false;
void solve() {
int n, x; cin >> n >> x;
int num[n+5];
for(int i = 1; i<=n; i++) cin >> num[i];
if(x == 0) {
vector<int> vec; vec.pb(num[1]);
for(int i = 2; i<=n; i++) {
if(num[i] > vec[vec.size()-1]) {vec.pb(num[i]); continue;}
int lo = 0;
int hi = vec.size()-1;
int res = vec.size()-1;
while(lo <= hi) {
int mid = (lo+hi)/2;
// cerr << "I: " << vec[mid] << " " << num[i] << endl;
if(vec[mid] < num[i]) lo = mid+1;
else hi = mid-1, res = mid;
}
// cerr << i << " " << res << endl;
vec[res] = num[i];
}
// for(auto v: vec) cerr << v << " ";
cout << vec.size() << endl;
return;
}
else if(x == 1e9) {
int l[n+5], r[n+5]; l[1] = 1; l[0] = 0;
vector<int> vec; vec.pb(num[1]);
for(int i = 2; i<=n; i++) {
if(num[i] > vec[vec.size()-1]) {vec.pb(num[i]); l[i] = vec.size(); continue;}
int lo = 0;
int hi = vec.size()-1;
int res = vec.size()-1;
while(lo <= hi) {
int mid = (lo+hi)/2;
// cerr << "I: " << vec[mid] << " " << num[i] << endl;
if(vec[mid] < num[i]) lo = mid+1;
else hi = mid-1, res = mid;
}
// cerr << i << " " << res << endl;
vec[res] = num[i];
l[i] = vec.size();
}
vec.clear();
vec.pb(num[n]); r[n] = 1, r[n+1] = 0;
for(int i = n-1; i>=1; i--) {
if(num[i] < vec[vec.size()-1]) {vec.pb(num[i]); r[i] = vec.size(); continue;}
int lo = 0;
int hi = vec.size()-1;
int res = vec.size()-1;
while(lo <= hi) {
int mid = (lo+hi)/2;
// cerr << "I: " << vec[mid] << " " << num[i] << endl;
if(vec[mid] > num[i]) lo = mid+1;
else hi = mid-1, res = mid;
}
// cerr << i << " " << res << endl;
vec[res] = num[i];
r[i] = vec.size();
}
// for(int i = 1; i<=n; i++) cerr << l[i] << " "; cerr << endl;
// for(int i = 1; i<=n; i++) cerr << r[i] << " "; cerr << endl;
int ans = 0;
for(int i = 0; i<=n; i++) {
ans = max(ans, l[i]+r[i+1]);
}
cout << ans << endl;
return;
}
int ans = 0;
int dp[n+5][3];
memset(dp, 0, sizeof(dp)); dp[n][1] = dp[n][0] = 1;
for(int i = n-1; i>=1; i--) {
for(int k = i+1; k<=n; k++) {
if(num[k] > num[i]) {
dp[i][0] = max(dp[i][0], dp[k][0]);
dp[i][1] = max(dp[i][1], dp[k][1]);
}
else if(num[i]-num[k] < x) {
dp[i][0] = max(dp[i][0], dp[k][1]);
}
}
dp[i][0] += 1, dp[i][1] += 1;
ans = max(ans, dp[i][0]);
}
// for(int i = 1; i<=n; i++) cerr << dp[i][0] << " " << dp[i][1] << endl; cerr << endl;
cout << ans << endl;
}
signed main() {
ios_base::sync_with_stdio(false);
int t = 1;
if(mutipletestcase) cin >> t;
while(t--) solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |