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>
#include <random>
#include <ext/pb_ds/assoc_container.hpp>
#define clr(X , val) memset(X , val , sizeof(X))
#define all(X) (X).begin() , (X).end()
#define rall(X) (X).rbegin() , (X).rend()
#define sz(X) (int)X.size()
//#define Judge
#define int intmax_t
#define endl '\n'
#define tab '\t'
#define mp make_pair
// Are u with me
using namespace std;
using namespace __gnu_pbds;
mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
template <class T> inline bool isSquare(T n) {
T s = sqrt(n);
return s * s == n || (s + 1) * (s + 1) == n;
}
typedef long long ll;
typedef unsigned long long ull;
template < class T > using indexed_set = tree < T , null_type , less < T > , rb_tree_tag , tree_order_statistics_node_update >;
template < class T > using indexed_multiset = tree < T , null_type , less_equal < T > , rb_tree_tag , tree_order_statistics_node_update >;
template < typename T1 > ostream &operator << (std::ostream &out, vector < T1 > &ar){for (int i = 0;i < ar.size();++i) out << ar[i] << " ";return out;}
template < typename T1 > istream &operator >> (std::istream &in , vector < T1 > &ar){for (int i = 0;i < ar.size();++i) in >> ar[i];return in;}
template < typename T1 > ostream &operator << (std::ostream &out, deque < T1 > &ar){for (int i = 0;i < ar.size();++i) out << ar[i] << " ";return out;}
template < typename T1 > istream &operator >> (std::istream &in , deque < T1 > &ar){for (int i = 0;i < ar.size();++i) in >> ar[i];return in;}
template < typename T1 > istream &operator >> (std::istream &in , vector < vector < T1 > > &ar){for (int i = 0;i < ar.size();++i){for (int j = 0;j < ar[i].size();++j) in >> ar[i][j];}return in;}
template < typename T1 > ostream &operator << (std::ostream &out , vector < vector < T1 > > &ar){for (int i = 0;i < ar.size();++i){for (int j = 0;j < ar[i].size();++j){ out << ar[i][j] << ' ';} out << '\n';}return out;}
template < typename T1 , typename T2 > istream &operator >> (std::istream &in , vector < pair < T1 , T2 > > &ar){for (int i = 0;i < ar.size();++i) in >> ar[i].first >> ar[i].second;return in;}
template < typename T1 , typename T2 > ostream &operator << (std::ostream &out, vector < pair < T1 , T2 > > &ar){for (int i = 0;i < ar.size();++i) out << ar[i].first << " " << ar[i].second << '\n';return out;}
template < typename T1 , typename T2 > ostream &operator << (std::ostream &out, deque < T1 , T2 > &ar){for (int i = 0;i < ar.size();++i) out << ar[i].first << ' ' << ar[i].second << '\n';return out;}
template < typename T1 , typename T2 > istream &operator >> (std::istream &in , deque < T1 , T2 > &ar){for (int i = 0;i < ar.size();++i) in >> ar[i].first >> ar[i].second;return in;}
template < typename T1 , typename T2 > ostream &operator << (std::ostream &out , pair < T1 , T2 > pp){out << pp.first << ' ' << pp.second;return out;}
constexpr int maxN = 1e3 + 100;
constexpr int maxM = 2e3 + 100;
const string alpha_ = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string alpha = "abcdefghijklmnopqrstuvwxyz";
constexpr long double EPS = 1e-8;
constexpr int X[] = {0, 1, 0, -1};
constexpr int Y[] = {1, 0, -1, 0};
constexpr int mod = 1e9 + 7;
void solve() { // check for T; don't use auto
int n , x;
cin >> n >> x;
vector < int > ar(n) , pref(n);
vector < int > st(n , numeric_limits < int >::max());
int ans = 0;
for (int i = 0;i < n;++i){
int a;cin >> a;
ar[i] = a;
auto pos = lower_bound(all(st) , a);
*pos = a;
pref[i] = pos - st.begin() + 1;
ans = max(ans , (int)pref[i]);
}
st.assign(n , numeric_limits < int >::max());
for (int i = n - 1;i >= 0;--i){
int pos = lower_bound(all(st) , -ar[i] + x) - st.begin();
ans = max(ans , pref[i] + pos);
auto pos_ = lower_bound(all(st) , -ar[i]);
*pos_ = -ar[i];
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
#ifdef Judge
freopen("cowjog.in" , "r" , stdin);
freopen("cowjog.out" , "w" , stdout);
#endif
//cin >> t;
while (t--){
solve();
}
return 0;
}
/* stuff you should look for
* int overflow, array bounds
* SPECIAL CASES (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
* DP: If you have overlapping , try to swap loops(or try to iterate from end)
* to read doubles use string and stod()
* if it says that one condition equals to another then try to solve this like equation
*/
# | 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... |