Submission #781959

#	Time	Username	Problem	Language	Result	Execution time	Memory
781959		aaron_dcoder	Global Warming (CEOI18_glo)	C++17	27 / 100	116 ms	8012 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> needed_info(N);
    vector<ll> currtime_best_revLDS_of_len(N+1,INFTY);
    currtime_best_revLDS_of_len[0] = -INFTY;
    
    for (ll i = (N-1); i >= 0; i--)
    {

        ll cindice = lower_bound(currtime_best_revLDS_of_len.begin(),currtime_best_revLDS_of_len.end()
        , -tempratures[i]) 
        - currtime_best_revLDS_of_len.begin();
        
        
        currtime_best_revLDS_of_len[cindice]=-tempratures[i];

        //dbg("array at step") << i;
 
        //for (ll i = 0; i < N; i++)
        //{
         //   dbg(":") << (currtime_best_revLDS_of_len[i]);
        //}

        needed_info[i] = lower_bound(currtime_best_revLDS_of_len.begin(),currtime_best_revLDS_of_len.end(), -(tempratures[i]-X)) 
        - currtime_best_revLDS_of_len.begin()-1ll;
        dbgv(needed_info[i]);
    }





    vector<ll> before_cheating_best_LIS_of_len(N+1,INFTY);
    before_cheating_best_LIS_of_len[0]=-INFTY;

    ll best = 1;

    for (ll i = 0; i < N; i++)
    {
        //dbg("array 2 at step") << i;
 
        //for (ll i = 0; i < N; i++)
        //{
        //    dbg(":") << (before_cheating_best_LIS_of_len[i]);
        //}


        best = max(best,
        needed_info[i]
        + (lower_bound(before_cheating_best_LIS_of_len.begin(),before_cheating_best_LIS_of_len.end(), tempratures[i]) - before_cheating_best_LIS_of_len.begin())
        );

        *lower_bound(before_cheating_best_LIS_of_len.begin(),before_cheating_best_LIS_of_len.end(), tempratures[i])
        =tempratures[i];

    
    }


    cout << max(best,lower_bound(before_cheating_best_LIS_of_len.begin(),before_cheating_best_LIS_of_len.end(), INFTY) 
        - before_cheating_best_LIS_of_len.begin()-1ll);    
    
}
/*
6 3
1 2 3 1 5 6
*/

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