Submission #781890

#TimeUsernameProblemLanguageResultExecution timeMemory
781890aaron_dcoderGlobal Warming (CEOI18_glo)C++17
58 / 100
2068 ms6920 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...