Submission #781890

#	Time	Username	Problem	Language	Result	Execution time	Memory
781890		aaron_dcoder	Global Warming (CEOI18_glo)	C++17	58 / 100	2068 ms	6920 KiB

glo

#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
    );
    
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25