이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#define NDEBUG
#ifdef NDEBUG
#define dbg(TXTMSG) (static_cast<int>(0))
#define dbgv(VARN) (static_cast<int>(0))
#else
#define dbg(TXTMSG) cerr << "\n" << TXTMSG
#define dbgv(VARN) cerr << "\n" << #VARN << " = "<<VARN << ", line: " << __LINE__ << "\n"
#define _GLIBCXX_DEBUG 1
#define _GLIBCXX_DEBUG_PEDANTIC 1
#endif
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll INFTY = 1e10;
#define var const auto&
int main() {
ll N,X;
cin >> N >> X;
vector<ll> tempratures(N);
for (ll i = 0; i < N; i++)
{
cin >> tempratures[i];
}
vector<ll> before_cheating_best_LIS_of_len(N+1,INFTY);
vector<ll> after_cheating_best_LIS_of_len(N+1,INFTY);
before_cheating_best_LIS_of_len[0]=-INFTY;
after_cheating_best_LIS_of_len[0]=-INFTY;
for (ll i = 0; i < N; i++)
{
ll newcheatlen = lower_bound(before_cheating_best_LIS_of_len.begin(),before_cheating_best_LIS_of_len.end(), tempratures[i]+X)-before_cheating_best_LIS_of_len.begin();
while (after_cheating_best_LIS_of_len[newcheatlen]>(tempratures[i]+X)) {
after_cheating_best_LIS_of_len[newcheatlen]=(tempratures[i]+X);
newcheatlen--;
}
*lower_bound(after_cheating_best_LIS_of_len.begin(),after_cheating_best_LIS_of_len.end(), tempratures[i]+X)
=tempratures[i]+X;
*lower_bound(before_cheating_best_LIS_of_len.begin(),before_cheating_best_LIS_of_len.end(), tempratures[i])
=tempratures[i];
//dbg("array at step");
//for (ll i = 0; i < N; i++)
//{
//dbg(":") << (before_cheating_best_LIS_of_len[i]) << ' '<< (after_cheating_best_LIS_of_len[i]);
//}
}
cout << (
lower_bound(after_cheating_best_LIS_of_len.begin(),after_cheating_best_LIS_of_len.end(), INFTY)
-after_cheating_best_LIS_of_len.begin()-1
);
}
# | 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... |