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>
#define int long long
using namespace std;
namespace std {
template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) {
out << "[";
for (int i = 0; i < (int)vec.size(); ++i) {
out << vec[i];
if (i + 1 < (int)vec.size())
out << ", ";
}
return out << "]";
}
} // namespace std
void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
cout << ' ' << H;
dbg_out(T...);
}
#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
vector<int> calcLIS(vector<int> vec) {
vector<int> curLis;
int n = vec.size();
vector<int> ret(n);
for (int i = 0; i < n; ++i) {
int pos =
lower_bound(curLis.begin(), curLis.end(), vec[i]) - curLis.begin();
ret[i] = pos + 1;
if (pos == (int)curLis.size())
curLis.push_back(vec[i]);
else
curLis[pos] = vec[i];
}
return ret;
}
signed main(void) {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, x;
cin >> n >> x;
vector<int> vec(n);
for (int &y : vec)
cin >> y;
vector<int> lisStart, lisEnd;
lisEnd = calcLIS(vec);
{
vector<int> vec2 = vec;
reverse(vec2.begin(), vec2.end());
for (int &y : vec2)
y *= -1;
lisStart = calcLIS(vec2);
reverse(lisStart.begin(), lisStart.end());
}
dbg(lisStart, lisEnd);
set<pair<int, int>> curChoices;
int sol = 0;
for (int i = 0; i < n; ++i) {
sol = max(sol, lisStart[i]);
auto it = curChoices.lower_bound({vec[i] + x, 0LL});
if (it != curChoices.begin()) {
--it;
sol = max(sol, it->second + lisStart[i]);
}
while ((it = curChoices.lower_bound({vec[i], 0LL})) != curChoices.end()) {
if (it->second <= lisStart[i])
curChoices.erase(it);
else
break;
}
it = curChoices.lower_bound({vec[i], 0LL});
if (it == curChoices.end() or it->first > vec[i])
curChoices.emplace(vec[i], lisStart[i]);
}
cout << sol << endl;
}
# | 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... |